Задача 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;
}
}
}
Моё решение можно найти здесь.
Auto comment: topic has been updated by re-wa-tl-ok (previous revision, new revision, compare).
Auto comment: topic has been updated by M1chael_Petrov (previous revision, new revision, compare).
this problem is exactly identical to 2D point update, 2D range sum query, as the transformation gives. In the first case, no point update necessary.
There are three optoins for the first case, wavelet tree, merge sort tree, or persistent segment tree. All of which are n log n, but wavelet tree allow bit-compression so it is actually n log n / 64 in memory, n log n time, which is the best solutoin.
The second case is a general unavoidable full on 2D queries, costing n log^2 n. but you can still choose between 2D BIT (if range small), red-black tree on segment tree, and 2d segment tree. If all queries are given ahead of time (offline) you can change the red-black tree on segment tree into BIT on segment tree after coordinate compression, which would be clearley the best option. If one of the range is dense (which is applicable here), use red-black tree on segment tree.
I think the solution to this problem is best presented by clearly splitting to a "reduction" component and an "data structure" component, I hope the examples I give show you why such a split is desirable.
There's yet another way: use sqrt decomposition online. $$$O(n\sqrt{n}\log(n))$$$. My idea is that when an element changes, you should change the left link too. Then use a similar idea as a merge sort tree, i.e. maintain a sorted list of elements in each block. It runs quite fast and beats all MO 3D implementations that I know. The problem (in Vietnamese): https://lqdoj.edu.vn/problem/diffquery2, my solution: https://gist.github.com/pt13762104/7a29af08b17fbffb87ca35e0ffcc0e88. Also I don't think you need the right link when you already have the left link.
Your nickname is very suitable for this way of solving the problem) Yes, I submitted a similar solution last year.
"Also I don't think you need the right link when you already have the left link." — It depends on what problem you're solving. To find the number of different elements, it is enough to store one link; and to find unique, you need 2, because both will have to go out of range. ([1, 2, 3, 3] has 2 unique elements: 1 and 2). Both tasks have their pros and cons in implementation.
As I understand it, here you are talking about different elements. Perhaps I really should have defined the "unique elements" at the beginning of the blog. Then there would be no misunderstandings.
I think this is a clearer solution.
We can still use Mo's algorithm for online queries. Maybe you think this is unbelievable, but this is really possible.
See this tutorial (In Chinese, but you can copy Markdown src here and do AI translation). The provided code is for problem P1903, which is almost the same as Problem 2 at the start of this blog