Офлайн обе задачи можно решить с помощью алгоритма Мо и 3DMo (существуют и другие способы, такие как scanline и т. д.), но есть задачи, в которых необходимо отвечать на запросы в онлайн-режиме. Решение с персистентным деревом отрезков, которое я слышал от Andrew-13, неплохое, но оно не поддерживает запросы на обновление. Итак, давайте разберёмся, как решить обе задачи.
Задача 1: $$$O(log(n)^2)$$$ на запрос с использованием 2D Неявного Дерева Отрезков
Что такое "уникальный" элемент на подотрезке? — элемент в подотрезке $$$a[ l, r ]$$$ считается уникальным, если он встречается ровно один раз в этом диапазоне, то есть его предыдущее вхождение (если оно есть) находится перед $$$l$$$, а следующее (если оно есть) — после $$$r$$$.
Введём определение: ссылка элемента $$$a_i$$$ — это указатель на ближайший равный ему элемент слева или справа. Если таких элементов нет, левая ссылка указывает на $$$-1$$$, а правая — на $$$n$$$.
Теперь нам нужно найти количество элементов на отрезке $$$[ l, r ]$$$, таких что их левая ссылка указывает на позицию < $$$l$$$, а правая — на позицию > $$$r$$$. Для этого построим массивы $$$future$$$ и $$$last$$$, содержащие ссылки на ближайшие равные элементы:
$$$future_i$$$ содержит индекс ближайшего элемента, равного $$$a_i$$$ справа (или $$$n$$$, если такого элемента нет).
$$$last_i$$$ содержит индекс ближайшего элемента, равного $$$a_i$$$ слева (или $$$-1$$$, если такого элемента нет).
Рассмотрим текущий запрос: $$$[ l, r ]$$$. Посчитаем количество элементов, у которых $$$future_i$$$ > $$$r$$$ и $$$last_i$$$ < $$$l$$$. Теперь все координаты положительны, так как $$$l$$$, $$$last_i$$$ < $$$n$$$ < $$$10^5$$$.
Таким образом, нам нужно посчитать количество точек ($$$x_i$$$, $$$y_i$$$) = ($$$1000000$$$ — $$$last_i$$$, $$$future_i$$$), которые находятся в верхней правой части плоскости относительно ($$$minX$$$, $$$minY$$$) = ($$$1000000$$$ — $$$l$$$, $$$r$$$). 2D Неявное Дерево Отрезков позволяет сделать это за $$$O(log(n)^2)$$$.
Это было бы решением, если бы не существовали точки:
которые находятся перед левой границей, а их правая ссылка пересекает правую границу.
которые находятся после правой границы, а их левая ссылка пересекает левую границу.
Поэтому нам нужно вычислить количество ненужных точек и вычесть их из общего ответа. Это можно реализовать с помощью простого Дерева Отрезков с Декартовыми Деревьями в узлах, так как нам нужно уметь отвечать на 2 запроса:
посчитать количество элементов на отрезке [ $$$0$$$, $$$l$$$ — $$$1$$$ ], у которых правая ссылка > $$$r$$$.
посчитать количество элементов на отрезке [ $$$r$$$ + $$$1$$$, $$$n$$$ — $$$1$$$ ], у которых левая ссылка < $$$l$$$.
Итог: Предподсчёт ~ $$$O(n * log(n)^2)$$$ Ответ на запрос ~ $$$O(log(n)^2)$$$.
Задача 2: $$$O(log(n)^2)$$$ на запрос с использованием 2D Неявного Дерева Отрезков
Что насчёт запросов на обновление? Заметим, что мы также можем легко отвечать на них за $$$O(log(n)^2)$$$. Обозначим:
$$$L$$$ — максимальная позиция в $$$a$$$, меньшая $$$i$$$, такая что $$$a_L$$$ = $$$X$$$; $$$F$$$ — минимальная позиция в $$$a$$$, большая $$$i$$$, такая что $$$a_F$$$ = $$$X$$$, где $$$X$$$ — это элемент в запросе на обновление. Если таких элементов нет, просто установим: $$$L$$$ = $$$-1$$$, $$$F$$$ = $$$n$$$.
При обновлении элемента $$$a_i$$$ изменяются только ссылки:
$$$a[i]$$$
$$$a[last_i]$$$
$$$a[future_i]$$$
$$$a[L]$$$
$$$a[F]$$$
Остаётся не забыть обновить Дерево Отрезков с Декартовыми Деревьями и точки на 2D плоскости Дерева Отрезков.
Итог: Предподсчёт ~ $$$O(n * log(n)^2)$$$ Ответ на запрос ~ $$$O(log(n)^2)$$$.
Моё решение можно найти здесь.
