Задача 1:Дан массив $$$a$$$ из $$$n$$$ < $$$10^5$$$ элементов от $$$1$$$ до $$$10^9$$$. Необходимо уметь находить количество уникальных элементов на отрезке от $$$l$$$ до $$$r$$$ ($$$0$$$ <= $$$l$$$ <= $$$r$$$ <= $$$n$$$ — $$$1$$$) в онлайн-режиме.
Задача 2:Дан массив $$$a$$$ из $$$n$$$ < $$$10^5$$$ элементов от $$$1$$$ до $$$10^9$$$. Необходимо уметь находить количество уникальных элементов на отрезке от $$$l$$$ до $$$r$$$ ($$$0$$$ <= $$$l$$$ <= $$$r$$$ <= $$$n$$$ — $$$1$$$) и изменять $$$a$$$: $$$a_i$$$ = $$$x$$$ в онлайн-режиме.
Офлайн обе задачи можно решить с помощью алгоритма Мо и 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)$$$.
Кодvoid Solve() {
int n; cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<int> base(n);
for (int i = 0; i < n; i++) {
base[i] = 0;
}
SegmentTree LAST(base);
map<int, int> last_id;
for (int i = 0; i < n; i++) {
last_id[a[i]] = -1;
}
vector<int> last(n);
for (int i = 0; i < n; i++) {
LAST.update(i, 0, last_id[a[i]]);
last[i] = 1'000'000 - last_id[a[i]];
last_id[a[i]] = i;
}
SegmentTree FUTURE(base);
map<int, int> future_id;
for (int i = 0; i < n; i++) {
future_id[a[i]] = n;
}
vector<int> future(n);
for (int i = n - 1; i >= 0; i--) {
FUTURE.update(i, 0, future_id[a[i]]);
future[i] = future_id[a[i]];
future_id[a[i]] = i;
}
vector<int> X;
for (int i = 0; i < n; i++) {
X.push_back(last[i]);
}
vector<int> Y;
for (int i = 0; i < n; i++) {
Y.push_back(future[i]);
}
vector<pair<int, int>> points;
for (int i = 0; i < n; i++) {
points.push_back({ X[i], Y[i] });
}
SegmentTree2D ST;
for (auto p : points) {
ST.update(p.first, p.second, 1);
}
int q; cin >> q;
for (int i = 0; i < q; i++) {
int l, r; cin >> l >> r;
--l;
--r;
int min_X = 1'000'000 - l;
int min_Y = r;
cout << ST.query(min_X + 1, min_Y + 1, inf, inf) - LAST.query_L(r + 1, n - 1, l - 1) - FUTURE.query_R(0, l - 1, r + 1) << endl;
}
}
Задача 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)$$$.
Кодvoid Solve() {
int n; cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<int> base(n);
for (int i = 0; i < n; i++) {
base[i] = 0;
}
SegmentTree LAST(base);
map<int, int> last_id;
for (int i = 0; i < n; i++) {
last_id[a[i]] = -1;
}
vector<int> last(n);
for (int i = 0; i < n; i++) {
LAST.update(i, 0, last_id[a[i]]);
last[i] = 1'000'000 - last_id[a[i]];
last_id[a[i]] = i;
}
SegmentTree FUTURE(base);
map<int, int> future_id;
for (int i = 0; i < n; i++) {
future_id[a[i]] = n;
}
vector<int> future(n);
for (int i = n - 1; i >= 0; i--) {
FUTURE.update(i, 0, future_id[a[i]]);
future[i] = future_id[a[i]];
future_id[a[i]] = i;
}
vector<int> X;
for (int i = 0; i < n; i++) {
X.push_back(last[i]);
}
vector<int> Y;
for (int i = 0; i < n; i++) {
Y.push_back(future[i]);
}
vector<pair<int, int>> points;
for (int i = 0; i < n; i++) {
points.push_back({ X[i], Y[i] });
}
SegmentTree2D ST;
for (auto p : points) {
ST.update(p.first, p.second, 1);
}
map<int, Treap_to_Find> POSITIONS;
for (int i = 0; i < n; i++) {
POSITIONS[a[i]].Add(i);
}
for (int i = 0; i < n; i++) {
if (POSITIONS[a[i]].Find(-1) == false) {
POSITIONS[a[i]].Add(-1);
}
if (POSITIONS[a[i]].Find(n) == false) {
POSITIONS[a[i]].Add(n);
}
}
int q; cin >> q;
for (int i = 0; i < q; i++) {
string Type; cin >> Type;
if (Type == "!") {
int pos, val; cin >> pos >> val;
--pos;
if (a[pos] == val) {
continue;
}
if (future[pos] != n) {
LAST.update(future[pos], pos, 1'000'000 - last[pos]);
ST.update(last[future[pos]], future[future[pos]], -1);
}
if (1'000'000 - last[pos] != -1) {
FUTURE.update(1'000'000 - last[pos], pos, future[pos]);
ST.update(last[1'000'000 - last[pos]], future[1'000'000 - last[pos]], -1);
}
if (future[pos] != n) {
last[future[pos]] = last[pos];
ST.update(last[future[pos]], future[future[pos]], 1);
}
if (1'000'000 - last[pos] != -1) {
future[1'000'000 - last[pos]] = future[pos];
ST.update(last[1'000'000 - last[pos]], future[1'000'000 - last[pos]], 1);
}
ST.update(last[pos], future[pos], -1);
POSITIONS[a[pos]].Del(pos);
POSITIONS[val].Add(pos);
if (POSITIONS[val].Find(-1) == false) {
POSITIONS[val].Add(-1);
}
if (POSITIONS[val].Find(n) == false) {
POSITIONS[val].Add(n);
}
int Last_for_val = POSITIONS[val].Find_ll(pos);
int Future_for_val = POSITIONS[val].Find_rr(pos);
LAST.update(pos, 1'000'000 - last[pos], Last_for_val);
FUTURE.update(pos, future[pos], Future_for_val);
last[pos] = 1'000'000 - POSITIONS[val].Find_ll(pos);
future[pos] = POSITIONS[val].Find_rr(pos);
a[pos] = val;
ST.update(last[pos], future[pos], 1);
if (Future_for_val != n) {
LAST.update(Future_for_val, Last_for_val, pos);
ST.update(last[Future_for_val], future[Future_for_val], -1);
}
if (Last_for_val != -1) {
FUTURE.update(Last_for_val, Future_for_val, pos);
ST.update(last[Last_for_val], future[Last_for_val], -1);
}
if (Future_for_val != n) {
last[Future_for_val] = 1'000'000 - pos;
ST.update(last[Future_for_val], future[Future_for_val], 1);
}
if (Last_for_val != -1) {
future[Last_for_val] = pos;
ST.update(last[Last_for_val], future[Last_for_val], 1);
}
}
else {
int l, r; cin >> l >> r;
--l;
--r;
int min_X = 1'000'000 - l;
int min_Y = r;
cout << ST.query(min_X + 1, min_Y + 1, inf, inf) - LAST.query_L(r + 1, n - 1, l - 1) - FUTURE.query_R(0, l - 1, r + 1) << endl;
}
}
}
Моё решение можно найти здесь.
