Как найти наиболее частое число и его частоту в массиве в диапазоне L, R наиболее эффективно?

Question

Допустим, нам задан массив A[] длины N, и мы должны ответить Q запросами, которые состоят из двух целых чисел L,R. Мы должны найти номер от A[L] до A[R], который имеет свою частоту не менее (R-L+1)/2. Если такого числа не существует, мы должны напечатать «Нет такого числа»

Я мог думать только о запуске частотного счетчика и первом получении наиболее частого числа в массиве от L to R. Затем подсчитайте его частоту.

Но требуется дополнительная оптимизация.

Ограничения:1<= N <= 3*10^5,, 1<=Q<=10^5, 1<=L<=R<=N

Answer 1

Я знаю, что в O((N + Q) * sqrt(N)) решение:

1. Давайте назовем ряд тяжелых если происходит, по крайней мере B раз в массиве. В массиве не более N/B тяжелых чисел.

2. Если сегмент запроса является «коротким» (R - L + 1 < 2 * B), мы можем ответить на него в O(B) времени (путем простого итерации по всем элементам диапазона).

3. Если сегмент запроса «длинный» (R - L + 1 >= 2 * B), частой элемент должен быть тяжелым. Мы можем перебирать все тяжелые числа и проверять, подходит ли хотя бы один из них (чтобы сделать это, мы можем прекомпретировать префиксные суммы числа вхождений для каждого тяжелого элемента и найти количество его вхождений в сегменте в постоянное время).

Если мы устанавливаем B = C * sqrt(N) для некоторой постоянной C это решение работает в O((N + Q) * sqrt(N)) времени и использует O(N * sqrt(N)) память. С правильно выбранным C и может вписываться во временное и запоминающее устройство.

Существует также рандомизированное решение, которое работает в O(N + Q * log N * k) времени.

1. Сохраним вектор положения вхождения для каждого уникального элемента в массиве. Теперь мы можем найти количество вхождений фиксированного элемента в фиксированном диапазоне в O(log N) времени (два бинарных поиска по вектору вхождений).

2. Для каждого запроса, мы будем делать следующее:

   • выбрать случайный элемент из сегмента
   • Проверьте количество его вхождений в O(log N) время, как описано выше
   • Если это частое достаточно, мы закончили. В противном случае мы выбираем другой случайный элемент и делаем то же самое.
   • Если существует частый элемент, вероятность его не выбирать - не более 1/2 для каждого испытания.Если мы делаем это k раз, вероятность не найти это (1/2)^k

При правильном выборе k (так что O(k * log N) на запрос достаточно быстро и (1/2)^k разумно мала), то это решение должно пройти ,

Оба решения просты в кодировании (первые просто нужны префиксные суммы, второй использует только вектор вхождений и двоичный поиск). Если бы мне пришлось закодировать один из них, я бы выбрал последний (первый может быть более болезненным, чтобы сжать во времени и ограничении памяти).