[Tutorial] Структура данных, учитывающая каждую пару на расстоянии не большем k ровно один раз

№	Пользователь	Рейтинг
1	Benq	3792
2	VivaciousAubergine	3647
3	Kevin114514	3603
4	jiangly	3583
5	strapple	3515
6	tourist	3470
7	dXqwq	3436
8	Radewoosh	3415
9	Otomachi_Una	3413
10	Um_nik	3376

№	Пользователь	Вклад
1	Qingyu	158
2	adamant	152
3	Um_nik	146
4	Dominater069	144
5	errorgorn	141
6	cry	139
7	Proof_by_QED	136
8	YuukiS	135
9	chromate00	134
9	TheScrasse	134

Недавно была следующая задача представлена на школьном BSUIR OPEN XIII:

Дан массив целых чисел и запросы изменения в точке. Нужно после каждого такого запроса отвечать в онлайне: сколько существует таких пар $$$i, j$$$, которую дают максимально возможную сумму и находятся на расстоянии не больше $$$k$$$.

Без онлайна — это почти баян с Канадской олимпиады для школьников (решается при помощи DCP-offline), но научимся делать в онлайне. По сути, я хочу научиться делать структуру данных, которая умеет учитывать каждую такую пару ровно один раз. Лично я умею ее делать за $$$log(n)$$$ на запрос.

Давайте дополним дерево отрезков до степени двойки (иначе работать не будет). Тогда у нас будет какое-то количество уровней, и при том, на каждом уровне у нас одиннаковое количество вершин. Тогда для удобство обозначим за $$$l_v, r_v$$$ это отрезок, за который отвечает поддерево, а за $$$lvl_{i, j}$$$ — вершину на $$$i$$$ уровнем под номером $$$j$$$ (у нас вершины на одном уровне идут в порядке возрастания правой границы). Также посчитаем за $$$nxt_v$$$ — самую последнюю вершину на уровне вершины $$$v$$$, для которой выполняется, что $$$r_{nxt} - r_v \leq k$$$ (другими словами, это самая дальняя вершина на уровне, для которой любая пара из этих поддеревьев образует подходящую пару)

Тогда утверждение, достаточно рассмотреть все пары в следующих поддеревьев:

Для каждой вершины $$$v$$$ скажем, что ответ для нее — это максимум ответа из левого/правого поддерева, а также рассмотреть оптимум в парах поддеревьев $$$v, nxt_v$$$, а также $$$v, 'nxt_v$$$, где $$$'nxt_v$$$ — это первая вершина левее на уровне $$$nxt_v$$$. А также взять два оптимума для поддерева размера $$$\leq k$$$.

Теперь как учесть каждую пару ровно один раз — мы не будет мержить две вершины, если у них предки тоже подходят (то есть, максимальное расстояние между парами вершин будет меньше или равно $$$k$$$). А вот этот факт уже очевидный.

Доказательство: проходит стрессы, а значит верно. Так как размеры всех деревьев степени двойки, и при том условие везде одиннаковое, то этот пересчет будет только на одном уровне (когда мы учитываем, что если предки подошли, то эту пару не учитываем). И при том, в этом случае будет задействованы не более $$$3$$$ вершин на этом уровне. (Иначе их предки были бы тоже актуальны). А в этом случае, данный алгоритм действительно каждую пару учтет ровно один раз, так как это будут все актуальные пары. А единственность очевидна, поэтому оставлю ее на доказательство читателя.

Мы научились учитывать каждую пару ровно один раз. Теперь нужно научиться обновлять делать изменение в точке. Давайте заметим, что при изменении вершины ответ поменяется только у предков, а это тривиально делается, а также у вершин, для которых наша была в качестве одного из двух правых. Мы эти вершины можем легко предпосчитать. А поэтому, мы должны пересчитать у них ответ, а затем рекурсивно обновить их родителей. И ввиду того, что нам нужно обновлять еще и родителей, то и получается $$$log^2$$$ (при том достаточно долгий, так как сам код пересчета достаточно тяжелый). (Либо же если аккуратно посмотреть доказательство, то у нас изменятся не так много интересных вершин дерева отрезков и получится $$$log$$$, но ниже предоставлена реализация за $$$log^2$$$)

Реализация

У меня код немножко кривой, ввиду того, что у меня левый сын имеет больший номер, но пусть будет. (и это впервые в жизни, когда я пожалел об этом).

#include "bits/stdc++.h"
 
using namespace std;
 
const int inf = 1e9 + 228;
 
struct SegTree {
    struct mx2node {
        pair<int, int> mx1 = {-inf, 0};
        pair<int, int> mx2 = {-inf, 0};
 
        mx2node() = default;
 
        void add(mx2node other) {
            if (other.mx1.first > mx1.first) {
                mx2 = mx1;
                mx1 = other.mx1;
            } else if (other.mx1.first == mx1.first) {
                mx1.second += other.mx1.second;
            } else if (other.mx1.first == mx2.first) {
                mx2.second += other.mx1.second;
            } else if (other.mx1.first > mx2.first) {
                mx2 = other.mx1;
            }
 
            if (other.mx2.first == mx2.first) {
                mx2.second += other.mx2.second;
            } else if (other.mx2.first > mx2.first) {
                mx2 = other.mx2;
            }
        }
    };
 
    struct node {
        int v;
        int l, r;
        int nxtl, nxtr;
        int ind_level;
        bool is_leaf;
 
        mx2node value;
        pair<int, long long> ans = {-inf, 0};
 
        node() = default;
    };
 
    static pair<int, long long> merge(pair<int, long long> a, pair<int, long long> b) {
        if (a.first == b.first) {
            return {a.first, a.second + b.second};
        }
        return max(a, b);
    }
 
    int n, k;
    vector<node> t;
    vector<vector<int>> lvl;
    vector<pair<int, int>> seg;
 
    void build_first(int v, int l, int r, int h) {
        if (lvl.size() == h) {
            lvl.emplace_back();
        }
        t[v].v = v;
        t[v].l = l, t[v].r = r;
        lvl[h].push_back(v);
        if (r - l == 1) {
            t[v].is_leaf = true;
            t[v].value = mx2node();
            t[v].ans = {-inf, 0};
            return;
        }
 
        int m = (l + r) / 2;
        build_first(v * 2 + 1, l, m, h + 1);
        build_first(v * 2, m, r, h + 1);
        t[v].is_leaf = false;
    }
 
    void calc_next(int h) {
        // v_r - v_l <= k
        int it = 0;
        auto cur = lvl[h];
        int sz = cur.size();
        for (int j = 0; j < sz; ++j) {
            auto i = cur[j];
            while (it + 1 < sz && max(abs(t[i].r - t[cur[it + 1]].l), abs(t[i].l - t[cur[it + 1]].r)) <= k) {
                ++it;
            }
            t[i].nxtr = -1;
            t[i].ind_level = j;
            if (max(abs(t[i].r - t[cur[it]].l), abs(t[i].l - t[cur[it]].r)) <= k && t[i].v != cur[it] && t[i].l != t[cur[it]].r) {
                t[i].nxtr = cur[it];
            }
        }
        it = sz - 1;
        for (int i = sz - 1; i >= 0; --i) {
            while (it - 1 >= 0 && max(abs(t[cur[i]].r - t[cur[it - 1]].l), abs(t[cur[i]].l - t[cur[it - 1]].r)) <= k) {
                --it;
            }
            t[cur[i]].nxtl = -1;
            if (max(abs(t[cur[i]].r - t[cur[it]].l), abs(t[cur[i]].l - t[cur[it]].r)) <= k && t[cur[i]].v != cur[it] && t[cur[it]].r != t[cur[it]].l) {
                t[cur[i]].nxtl = cur[it];
            }
        }
    }
 
    bool valid(const node &v, const node &u) {
        if (v.v == 1) {
            return true;
        }
        const node &a = t[v.v / 2];
        const node &b = t[u.v / 2];
        if (max(abs(b.r - a.l), abs(b.l - a.r)) <= k)
            return false;
        return true;
    }
 
    pair<int, long long> merge(const node &v, const node &u) {
        if (!valid(v, u))
            return {-inf, 0};
        if (v.v == u.v) {
            if (v.value.mx1.second > 1) {
                return {2 * v.value.mx1.first, 1ll * v.value.mx1.second * (v.value.mx1.second - 1) / 2};
            }
            return {v.value.mx1.first + v.value.mx2.first, 1ll * v.value.mx1.second * v.value.mx2.second};
        } else {
            return {v.value.mx1.first + u.value.mx1.first, 1ll * v.value.mx1.second * u.value.mx1.second};
        }
    }
 
    void update_node(node &v, int h, int first_run = 1) {
        if (!v.is_leaf) {
            v.value = mx2node();
            v.value.add(t[v.v * 2 + 1].value);
            v.value.add(t[v.v * 2].value);
        }
 
        pair<int, long long> ans = {-inf, 0};
 
        if (v.nxtr != -1) {
            ans = merge(ans, merge(v, t[v.nxtr]));
            if (t[v.nxtr].ind_level - 1 >= 0) {
                int nxt = lvl[h][t[v.nxtr].ind_level - 1];
                if (nxt != v.v) {
                    ans = merge(ans, merge(v, t[nxt]));
                }
            }
        }
        if (first_run) {
            if (v.nxtl != -1) {
                update_node(t[v.nxtl], h, false);
                if (t[v.nxtl].ind_level + 1 < (int) lvl[h].size()) {
                    int nxt = lvl[h][t[v.nxtl].ind_level + 1];
                    if (nxt != v.v) {
                        update_node(t[nxt], h, false);
                    }
                }
            }
        }
 
        if (v.r - v.l <= k) {
            ans = merge(ans, merge(v, v));
        }
 
        v.ans = ans;
        if (!v.is_leaf) {
            v.ans = merge(v.ans, t[v.v * 2 + 1].ans);
            v.ans = merge(v.ans, t[v.v * 2].ans);
        }
        if (!first_run && v.v != 1) {
            update_node(t[v.v / 2], h - 1, false);
        }
    }
 
    void update(int v, int l, int r, int pos, int value, int h = 0) {
        if (r - l == 1) {
            t[v].value = mx2node();
            t[v].value.mx1 = {value, 1};
            update_node(t[v], h);
            return;
        }
 
        int m = (l + r) / 2;
        if (pos < m) {
            update(v * 2 + 1, l, m, pos, value, h + 1);
        } else {
            update(v * 2, m, r, pos, value, h + 1);
        }
        update_node(t[v], h);
    }
 
    void update(int pos, int value) {
        update(1, 0, n, pos, value, 0);
    }
 
    SegTree(int _n, int k) : k(k) {
        int sz = 1;
        while (sz < _n) {
            sz *= 2;
        }
        n = sz;
        t.resize(2 * sz);
 
        build_first(1, 0, n, 0);
        for (int i = 0; i < (int) lvl.size(); ++i) {
            calc_next(i);
        }
    }
 
    pair<int, long long> get() {
        return t[1].ans;
    }
};
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    SegTree t(n, k);
    for (int i = 0; i < n; ++i) {
        t.update(i, a[i]);
    }
    pair<int, long long> ans = t.get();
    cout << ans.first << ' ' << ans.second << '\n';
    int q;
    cin >> q;
    while (q--) {
        int pos, value;
        cin >> pos >> value;
        pos = (pos + ans.first + ans.second) % n + 1;
        t.update(pos - 1, value);
        ans = t.get();
        cout << ans.first << ' ' << ans.second << '\n';
    }
}

Комментарии (5)

Написать комментарий?

serialcomder

12 месяцев назад, скрыть # |

+22

getting rid of that negative contribution i see :)

→ Ответить

Seferoglu

← Rev. 2 →

wth is DCP offline?

tch1cherin

12 месяцев назад, скрыть # ^ |

It's "dynamic connectivity problem offline". But in the context of this blog it means the idea of that solution of the dynamic connectivity problem (in short: build a segment tree on the times of the queries where in each vertex [tl, tr] you store the edges that are alive in this segment) not the problem itself. You can also read about the general technique here.

cool, thanks

FairyWinx

This is not a dcp, but an online solution to this problem :)

Блог пользователя FairyWinx