T3 的可持久化线段树标记永久化区间加法套二分做法

__ryp__ · 2024-09-23 11:28:54 · 个人记录

考虑到题目中的操作实际上就是给区间加上某个值，询问就是问某点和第一次大于等于 k 的时间。

考虑到可以直接用可持久化线段树模拟这个过程。

可持久化线段树是可以用标记永久化的方法来实现某些区间操作的。具体来说，我们不将某个点上的标记下传，而是在询问时一路加上所有标记。

然后二分一个最早的树即可。实现不难。

#include <iostream>
using namespace std;
using i64 = long long;
const int N = 1e6 + 10;
struct node { i64 s; int l, r; } sg[20 * N];
int rt[N], id[N], cnt = 0;

void upd (int &u, int v, int x, int y, int l, int r, i64 k)
{
    int mid = (x + y) / 2;
    sg[u = ++cnt] = sg[v];
    if (l <= x && y <= r) return sg[u].s += k, void ();
    if (l <= mid) upd (sg[u].l, sg[v].l, x, mid, l, r, k);
    if (r > mid) upd (sg[u].r, sg[v].r, mid + 1, y, l, r, k);
}

i64 qry (int u, int x, int y, int p, i64 tag)
{
    int mid = (x + y) / 2;
    if (x == y) return sg[u].s + tag;
    if (p <= mid) return qry (sg[u].l, x, mid, p, tag + sg[u].s);
    else return qry (sg[u].r, mid + 1, y, p, tag + sg[u].s);
}

int main (void)
{
    int n, q, qid = 0;

    cin.tie (0)->sync_with_stdio (false);
    cin >> n >> q;
    for (int i = 1; i <= q; i++) {
        int opt;

        cin >> opt;
        if (opt == 1) {
            int x;
            i64 y, k;
            cin >> x >> y >> k;
            id[++qid] = i, upd (rt[qid], rt[qid - 1], 1, n, x, y, k);
        }
        else {
            int l = 1, r = qid, ans = -1, x;
            i64 y;

            cin >> x >> y;

            if (qry (rt[qid], 1, n, x, 0) < y) {
                cout << "0\n";
                continue;
            }

            while (l <= r) {
                int mid = (l + r) / 2;
                if (qry (rt[mid], 1, n, x, 0) >= y) r = (ans = mid) - 1;
                else l = mid + 1;
            }

            cout << id[ans] << '\n';
        }
    }
    return 0;