Граф количество прямоугольников

Question

Существует NxM сетки присутствует с нумерацией, как 1,2,...NM (нумерация выполняется ряд мудр. 1-й ряд будет содержать число от к M, вторая строка будет содержать М + 1 к 2M и так далее).

Существует также список дано Х чисел, находится в диапазоне от 1 к Н.М..

Проблема: * Количество общее количество прямоугольников со сторонами по линии сетки и содержит ровно K точек из списка X для каждого K в диапазоне от до длины X ,

Пример стоит более 1000 слов:

Let N=2, M=2 and X=[1,2]. 
Rectangle containing 0 points: 3 
Rectangle containing 1 points: 4 
Rectangle containing 2 points: 2 

Мой подход

Я знаю, что общее число прямоугольников возможных из этой сетки n(n+1)m(m+1)/4, но не мог думать ни о чем другом.

РЕДАКТИРОВАТЬ
1 ≤ N, M ≤ 10^7
1 ≤ длина X ≤ 10^5
1 ≤ элементов в списке X ≤ N * M

Answer 1

Он O(n^2 * m^2) подход.

Число строк сетки строк как row[0], ..., row[n] и линии сетки столбцов, как column[0], ..., column[n]. Пусть f[x][y] обозначает количество точек в X, содержащихся в прямоугольнике с верхней стороной - row[0], нижняя сторона - row[x], левая сторона - column[0], правая сторона - column[y]. Обратите внимание, что вы можете рассчитать f в восходящем приближении только для O(n*m) времени (это динамическое программирование).

Теперь для каждого прямоугольника с верхней стороны - row[x1], нижняя сторона - row[x2], левая сторона - column[y1], левая сторона column[y2] (x1<x2, y1<y2) можно рассчитать общее количество X точек в нем быть f[x2][y2]-f[x1][y2]-f[x2][y1]+f[x1][y1]. После того, как вы вычислите номер, который вы положили на карту подсчета, которая связывает количество точек в X, содержащихся в текущем прямоугольнике, сколько раз вы столкнулись с этим числом. Вы можете использовать hashmap.

Всего у вас есть O(n^2*m^2).

В вашем примере, для f у вас есть:

f[0][0] = f[0][1] = f[0][2] = f[1][0] = f[2][0] = 0 
f[1][1] = 1 
f[1][2] = 2 
f[2][1] = 1 
f[2][2] = 2 

Теперь, для прямоугольника row[0], row[1], column[1], column[2] у вас есть количество точек в X, которые содержатся в этом прямоугольнике быть:

number = f[1][2]-f[0][2]-f[1][1]+f[0][0] = 2-0-1+0 = 1 

что правильно.

Обратите внимание, что подход с грубой силой имеет сложность O(n^4 * m^4).