L. Различные на отрезке

Дан массив. На каждый запрос $(l, r)$ нужно сказать, сколько различных значений встречается среди $a_l, \ldots, a_r$.

Обновлений нет, все запросы известны заранее - значит, можно отвечать на них не в том порядке, в котором они заданы. Это и есть алгоритм Мо.

Два указателя, которые не откатываются

Держим текущий отрезок $[l, r]$ и счётчики cnt[v] - сколько раз значение $v$ встречается внутри. Отдельно храним число различных: при cnt[v]++ с нуля до единицы оно растёт, при cnt[v]-- до нуля - падает.

auto add = [&](int i) { if (cnt[a[i]]++ == 0) distinct++; };
auto del = [&](int i) { if (--cnt[a[i]] == 0) distinct--; };

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

Порядок, в котором сдвиги малы

Разобьём индексы на блоки длины $B$ и отсортируем запросы по паре (блок левого конца, правый конец).

• внутри блока левый конец гуляет по блоку: $O(B)$ на запрос, всего $O(qB)$;
• внутри блока правый конец только растёт: $O(n)$ на блок, всего $O(n^2 / B)$.

При $B = n / \sqrt{q}$ обе суммы равны $O(n\sqrt{q})$. Обычная корневая $B = \sqrt{n}$ тоже проходит.

Змейка

В чётных блоках сортируем по правому концу по возрастанию, в нечётных - по убыванию. Тогда при переходе к следующему блоку правый указатель не откатывается в начало. Это не меняет асимптотику, но на практике ускоряет примерно в полтора раза.

Подробнее: «Алгоритм Мо».

В первой строке - число $n$ ($1 \le n \le 10^5$).

Во второй строке - $n$ чисел $a_i$ ($1 \le a_i \le 10^6$).

В третьей строке - число запросов $q$ ($1 \le q \le 10^5$).

В следующих $q$ строках - пары $l$ и $r$ ($1 \le l \le r \le n$).

Для каждого запроса выведите количество различных значений на отрезке.