Frequent values - 2 (Editorial)

Задача отличается от задачи 3838 "Частые значения" увеличенными ограничениями на $n$ и $q$ . Последовательность задаётся один раз и не изменяется, поэтому для ответа на запросы воспользуемся разреженной таблицей (Sparse Table), которая находит максимум на отрезке за $O (1)$ .

Блоки равных элементов. Последовательность упорядочена по неубыванию, поэтому равные элементы стоят подряд и образуют блоки. Количество вхождений значения на отрезке $[i; j]$ равно длине пересечения его блока с этим отрезком.

Массив $b$ . Построим массив $b$ , в котором $b_{i}$ b_i — номер элемента $a_{i}$ a_i внутри своего блока, то есть количество элементов, равных $a_{i}$ a_i, от начала блока до позиции $i$ включительно:

$b_{1} = 1$ b_1 = 1;
$b_{i} = b_{i - 1} + 1$ b_i = b_{i-1} + 1, если $a_{i} = a_{i - 1}$ a_i = a_{i-1}, и $b_{i} = 1$ b_i = 1 в противном случае.

На рисунке показаны массив $a = (3, 3, 5, 9, 9, 9, 9, 10, 10)$ a = (3, 3, 5, 9, 9, 9, 9, 10, 10) и построенный по нему массив $b$ . Блоки равных элементов выделены чередующимися цветами, над каждым блоком указана его длина.

Внутри блока значения $b$ последовательно принимают значения $1, 2, 3, \dots$ 1, 2, 3, \ldots. Поэтому наибольшее значение $b$ в блоке достигается в его последнем элементе и равно длине блока. Эти элементы выделены оранжевым цветом.

Ответ на запрос. Рассмотрим запрос $[i; j]$ .

Если $a_{i} = a_{j}$ a_i = a_j, то все элементы отрезка равны, и ответ равен $j - i + 1$ j - i + 1.
Иначе отрезок пересекает не менее двух блоков. Пусть $k$ — самый правый индекс, для которого $a_{k} = a_{i}$ a_k = a_i, то есть последняя позиция первого блока. Значение $a_{i}$ a_i встречается на отрезке $k - i + 1$ k - i + 1 раз.

Все остальные блоки, пересекающие отрезок, начинаются внутри него — на позиции $k + 1$ k + 1 или правее. Поэтому для любой позиции $t \in [k + 1; j]$ t \in [k + 1; j] значение $b_{t}$ b_t отсчитывается от начала блока, лежащего внутри отрезка, и не учитывает лишних элементов. Последний блок может обрываться на позиции $j$ , но тогда $b_{j}$ b_j равно количеству его элементов на отрезке. Следовательно, наибольшее количество вхождений среди этих блоков равно максимуму $b$ на $[k + 1; j]$ [k + 1; j], и ответ на запрос равен

max (k - i + 1, RMQ (k + 1, j)),

\max\bigl(k - i + 1, \mathit{RMQ}(k + 1, j)\bigr),

где $RMQ (l, r)$ \mathit{RMQ}(l, r) — максимум элементов $b_{l}, \dots, b_{r}$ b_l, \ldots, b_r.

Первый блок нельзя обработать с помощью массива $b$ : он может начинаться левее позиции $i$ , и тогда значения $b$ в нём учитывают элементы, не входящие в отрезок.

Позицию $k$ находим бинарным поиском: это позиция, предшествующая первому элементу, большему $a_{i}$ a_i. Поскольку $a_{j} > a_{i}$ a_j > a_i, такой элемент существует на отрезке $[i + 1; j]$ [i + 1; j].

Разреженная таблица. Таблица строится по массиву $b$ и хранит не индексы, а сами максимальные значения: позиция максимума в этой задаче не нужна.

Сложность. Построение разреженной таблицы для каждого теста выполняется за $O (n lo g n)$ O(n \log n). Запрос состоит из бинарного поиска за $O (lo g n)$ O(\log n) и запроса максимума за $O (1)$ . Итоговая сложность теста составляет $O (n lo g n + q lo g n)$ O(n \log n + q \log n), используемая память — $O (n lo g n)$ O(n \log n).

Пример

Рассмотрим пример. Массив $a$ и построенный по нему массив $b$ имеют следующий вид:

$i$	1	2	3	4	5	6	7	8	9	10
$a_{i}$ \boldsymbol{a_i}	$- 1$	$- 1$	1	1	1	1	3	10	10	10
$b_{i}$ \boldsymbol{b_i}	1	2	1	2	3	4	1	1	2	3

Массив состоит из четырёх блоков: $(- 1, - 1)$ , $(1, 1, 1, 1)$ (1, 1, 1, 1), $(3)$ и $(10, 10, 10)$ (10, 10, 10) длины $2$ , $4$ , $1$ и $3$ соответственно. Последний элемент каждого блока содержит в $b$ длину блока.

Запрос $[2; 3]$ . Так как $a_{2} = - 1 \neq = a_{3} = 1$ a_2 = -1 \ne a_3 = 1, находим $k = 2$ k = 2. Первый блок даёт $2 - 2 + 1 = 1$ 2 - 2 + 1 = 1 вхождение, $RMQ (3, 3) = b_{3} = 1$ \mathit{RMQ}(3, 3) = b_3 = 1. Ответ равен $max (1, 1) = 1$ \max(1, 1) = 1.

Запрос $[1; 10]$ . Так как $a_{1} = - 1 \neq = a_{10} = 10$ a_1 = -1 \ne a_{10} = 10, находим $k = 2$ k = 2. Первый блок даёт $2$ вхождения, $RMQ (3, 10) = max (1, 2, 3, 4, 1, 1, 2, 3) = 4$ \mathit{RMQ}(3, 10) = \max(1, 2, 3, 4, 1, 1, 2, 3) = 4. Ответ равен $max (2, 4) = 4$ \max(2, 4) = 4: значение $1$ встречается $4$ раза.

Запрос $[5; 10]$ . Так как $a_{5} = 1 \neq = a_{10} = 10$ a_5 = 1 \ne a_{10} = 10, находим $k = 6$ k = 6. Первый блок даёт $6 - 5 + 1 = 2$ 6 - 5 + 1 = 2 вхождения, $RMQ (7, 10) = max (1, 1, 2, 3) = 3$ \mathit{RMQ}(7, 10) = \max(1, 1, 2, 3) = 3. Ответ равен $max (2, 3) = 3$ \max(2, 3) = 3.

Этот запрос показывает, почему первый блок обрабатывается отдельно. Значения $b_{5} = 3$ b_5 = 3 и $b_{6} = 4$ b_6 = 4 учитывают элементы $a_{3}$ a_3 и $a_{4}$ a_4, которые лежат вне отрезка. Если бы мы вычислили максимум $b$ на всём отрезке $[5; 10]$ , то получили бы неверный ответ $4$ .

Реализация алгоритма

Объявим константы и массивы. Входная последовательность хранится в массиве $a$ , вспомогательный массив $b$ описан выше. Значение $lg2 [len]$ равно $⌊ lo g_{2} len ⌋$ \lfloor \log_2 \mathit{len} \rfloor. Разреженная таблица $mas [i] [j]$ \mathit{mas}[i][j] хранит максимум элементов $b$ на отрезке $[i; i + 2^{j} - 1]$ [i; i + 2^j - 1]. Поскольку $2^{18} \leq 5 \cdot 1 0^{5} < 2^{19}$ 2^{18} \le 5 \cdot 10^5 < 2^{19}, значения $j$ не превышают $18$ , и для второго измерения достаточно $LOGMAX = 19$ \mathit{LOGMAX} = 19.

#define MAX 500010
#define LOGMAX 19
using namespace std;
int a[MAX], b[MAX], lg2[MAX];
int mas[MAX][LOGMAX];

Функция Build_RMQ_Array строит разреженную таблицу по массиву $b$ .

void Build_RMQ_Array(int* b)
{
  for (int i = 1; i <= n; i++) mas[i][0] = b[i];
  for (int j = 1; 1 << j <= n; j++)
    for (int i = 1; i + (1 << j) - 1 <= n; i++)
      mas[i][j] = max(mas[i][j - 1], mas[i + (1 << (j - 1))][j - 1]);
}

C++

Функция RMQ возвращает максимум элементов $b_{i}, \dots, b_{j}$ b_i, \ldots, b_j за $O (1)$ .

int RMQ(int i, int j)
{
  int k = lg2[j - i + 1];
  return max(mas[i][k], mas[j - (1 << k) + 1][k]);
}

Основная часть программы. Значения $lg2$ вычисляются один раз для всех длин до $MAX$ и используются во всех тестах.

for (int i = 2; i < MAX; i++) lg2[i] = lg2[i / 2] + 1;

Обрабатываем тесты, пока $n \neq = 0$ n \ne 0. Читаем последовательность $a$ и одновременно строим массив $b$ : если элемент равен предыдущему, его номер в блоке на единицу больше, иначе с него начинается новый блок.

while (scanf("%d %d", &n, &q), n)
{
  scanf("%d", &a[1]); b[1] = 1;
  for (i = 2; i <= n; i++)
  {
    scanf("%d", &a[i]);
    if (a[i] == a[i - 1]) b[i] = b[i - 1] + 1; else b[i] = 1;
  }

C++

Строим разреженную таблицу по массиву $b$ .

  Build_RMQ_Array(b);

Последовательно обрабатываем $q$ запросов. Если $a_{Left} = a_{Right}$ a_{\mathit{Left}} = a_{\mathit{Right}}, то все элементы отрезка равны, и ответ равен $Right - Left + 1$ \mathit{Right} - \mathit{Left} + 1.

  for (i = 0; i < q; i++)
  {
    scanf("%d %d", &Left, &Right);
    if (a[Left] == a[Right]) printf("%d\n", Right - Left + 1);

Иначе находим $LeftEnd$ — последнюю позицию блока, содержащего $a_{Left}$ a_{\mathit{Left}}. Функция upper_bound на отрезке $[Left; Right)$ [\mathit{Left}; \mathit{Right}) возвращает указатель на первый элемент, больший $a_{Left}$ a_{\mathit{Left}}. Такой элемент существует, так как $a_{Right} > a_{Left}$ a_{\mathit{Right}} > a_{\mathit{Left}}. Предыдущая позиция и есть $LeftEnd$ . Ответ равен $max (LeftEnd - Left + 1, RMQ (LeftEnd + 1, Right))$ \max\bigl(\mathit{LeftEnd} - \mathit{Left} + 1, \mathit{RMQ}(\mathit{LeftEnd} + 1, \mathit{Right})\bigr).

    else
    {
      int LeftEnd =
          (int)(upper_bound(a + Left, a + Right, a[Left]) - a) - 1;
      res = max(LeftEnd - Left + 1, RMQ(LeftEnd + 1, Right));
      printf("%d\n", res);
    }
  }
}

C++