Как мы можем найти количество различных элементов в данной подматрице?
Дана N * N матрица и Q запросов для одной и той же заданной матрицы. Каждый запрос имеет форму x1, y1, x2, y2. Мы должны найти число различных элементов в подматрице, определенных (x1, y1) и (x2, y2) как верхний левый и нижний правый угол соответственно.
Ограничения: N<= 300
Q<= 10 ^ 5
Я использую наивный подход итерации по субматрице для каждого запроса. Есть ли лучший подход?
Решение
Это зависит от того, сколько запросов вы можете ожидать, и количества идентичных запросов, которые вы можете ожидать.
Один из подходов состоит в том, чтобы «запоминать» запросы, просто сохранять каждый запрос и результат и искать его, прежде чем выполнять более серьезную работу.
Более проблемный подход — вероятно, то, к чему стремится ваш учитель — состоит в том, чтобы вычислить различные элементы (0, 0, x, y) для каждого (справа, снизу) = (x, y). Тогда это простая теория множеств для обработки каждого запроса. Но выполнение оригинальных вычислений занимает много времени.
Не забудьте добавить ссылку на этот SO-ответ.
Другие решения
Других решений пока нет …