线段树分裂线段树合并板子LUOGU5494

#include <bits/stdc++.h>

using namespace std;
const int maxn = 2e5 + 5;
typedef long long ll;
int ls[maxn * 60], rs[maxn * 60], tot;
int pool[maxn * 60], lj;
int newnode() { return lj ? pool[lj--] : ++tot; }

ll sm[maxn * 60];
int n, m;
int rt[maxn], nowrt = 1;
void del(int p) {
    pool[++lj] = p;
    ls[p] = rs[p] = sm[p] = 0;
}
void maketree(int &p, int l, int r) {
    p = ++tot;
    if (l == r) {
        scanf("%lld", &sm[p]);
        return;
    }
    int mid = (l + r) >> 1;
    maketree(ls[p], l, mid);
    maketree(rs[p], mid + 1, r);
    sm[p] = sm[ls[p]] + sm[rs[p]];
}
void ins(int &p, int l, int r, int num, int x) {
    if (!p)
        p = newnode();
    sm[p] += num;
    if (l == r) {
        return;
    }

    int mid = (l + r) >> 1;
    if (x <= mid)
        ins(ls[p], l, mid, num, x);
    else
        ins(rs[p], mid + 1, r, num, x);
}
int merge(int x, int y) {
    if ((!x) || (!y))
        return x + y;
    ls[x] = merge(ls[x], ls[y]);
    rs[x] = merge(rs[x], rs[y]);
    sm[x] += sm[y];
    del(y);
    return x;
}
void split(int x, int &y, ll k) {
    if (x == 0)
        return;
    y = newnode();
    ll lsz = sm[ls[x]];
    if (k > lsz) {
        split(rs[x], rs[y], k - lsz);
    } else {
        rs[y] = rs[x];
        rs[x] = 0;
    }
    if (k < lsz) {
        split(ls[x], ls[y], k);
    }
    sm[y] = sm[x] - k;
    sm[x] = k;
    return;
}
ll query(int &p, int l, int r, int x, int y) {
    if (!p)
        return 0;
    if (x <= l && r <= y) {
        return sm[p];
    }
    int mid = (l + r) >> 1;
    if (y <= mid)
        return query(ls[p], l, mid, x, y);
    else if (x > mid)
        return query(rs[p], mid + 1, r, x, y);
    else
        return query(ls[p], l, mid, x, y) + query(rs[p], mid + 1, r, x, y);
}
int getk(int p, int l, int r, int k) {
    if (l == r)
        return l;
    int mid = (l + r) >> 1;
    if (k > sm[ls[p]])
        return getk(rs[p], mid + 1, r, k - sm[ls[p]]);
    else
        return getk(ls[p], l, mid, k);
}
int main() {
    scanf("%d%d", &n, &m);
    maketree(rt[1], 1, n);
    int opt, p, x, y, t, q, k;
    for (int i = 1; i <= m; i++) {
        scanf("%d", &opt);
        if (opt == 0) {
            scanf("%d%d%d", &p, &x, &y);
            ll sz1 = query(rt[p], 1, n, 1, y);
            ll sz2 = query(rt[p], 1, n, x, y);
            ++nowrt;
            split(rt[p], rt[nowrt], sz1 - sz2);
            int tmprt = 0;
            split(rt[nowrt], tmprt, sz2);
            rt[p] = merge(rt[p], tmprt);
        } else if (opt == 1) {
            scanf("%d%d", &p, &t);
            rt[p] = merge(rt[p], rt[t]);
        } else if (opt == 2) {
            scanf("%d%d%d", &p, &x, &q);
            ins(rt[p], 1, n, x, q);
        } else if (opt == 3) {
            scanf("%d%d%d", &p, &x, &y);
            printf("%lld\n", query(rt[p], 1, n, x, y));
        } else {
            scanf("%d%d", &p, &k);
            if (sm[rt[p]] < k)
                puts("-1");
            else {
                printf("%d\n", getk(rt[p], 1, n, k));
            }
        }
    }
    return 0;
}