剪贴板 4b5cr1rk

```cpp #include <cstdio> #include <iostream> #define ll long long constexpr auto N = 1000010; using namespace std; int n, m; class ValSegTre { private: int ncnt = 0; struct Tre { int l, r; ll dat; } tre[N << 2]; int loop[N], used = 0; #define D(x) tre[x].dat #define L(x) tre[x].l #define R(x) tre[x].r void newnode(int &id) { id = used ? loop[used--] : ++ncnt; } void del(int id) { loop[++used] = id; D(id) = L(id) = R(id) = 0; } void update(int id) { D(id) = D(L(id)) + D(R(id)); } public: ll Dat(int id) { return tre[id].dat; } int rt[N], rcnt = 1; void add(int &id, int l, int r, int x, ll va) { if (!id) newnode(id); if (l == r) { D(id) += va; return; } int mid = (l + r) >> 1; if (x <= mid) add(L(id), l, mid, x, va); else add(R(id), mid + 1, r, x, va); update(id); } ll ask(int id, int l, int r, int ql, int qr) { if (!id || ql > r || qr < l) return 0; if (ql <= l && r <= qr) return D(id); int mid = (l + r) >> 1; return ask(L(id), l, mid, ql, qr) + ask(R(id), mid + 1, r, ql, qr); } int merge(int x, int y) { if (!x || !y) return x + y; D(x) += D(y); L(x) = merge(L(x), L(y)); R(x) = merge(R(x), R(y)); del(y); return x; } void split(int x, int &y, ll k) { if (!x) return; newnode(y); ll v = D(L(x)); if (k > v) split(R(x), R(y), k - v); else swap(R(x), R(y)); if (k < v) split(L(x), L(y), k); D(y) = D(x) - k; D(x) = k; return; } int kth(int x, int l, int r, int k) { if (l == r) return l; int mid = (l + r) >> 1; if (k <= D(L(x))) return kth(L(x), l, mid, k); else return kth(R(x), mid + 1, r, k - D(L(x))); } } TRE; int main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin >> n >> m; for (int i = 1, t; i <= n; ++i) cin >> t, TRE.add(TRE.rt[1], 1, n, i, t); while (m--) { int op; cin >> op; if (!op) { int p, x, y; cin >> p >> x >> y; ll k1 = TRE.ask(TRE.rt[p], 1, n, 1, y), k2 = TRE.ask(TRE.rt[p], 1, n, x, y); int temp = 0; TRE.split(TRE.rt[p], TRE.rt[++TRE.rcnt], k1 - k2); TRE.split(TRE.rt[TRE.rcnt], temp, k2); TRE.rt[p] = TRE.merge(TRE.rt[p], temp); } else if (op == 1) { int p, t; cin >> p >> t; TRE.rt[p] = TRE.merge(TRE.rt[p], TRE.rt[t]); } else if (op == 2) { int p, x, q; cin >> p >> x >> q; TRE.add(TRE.rt[p], 1, n, q, x); } else if (op == 3) { int p, x, y; cin >> p >> x >> y; cout << TRE.ask(TRE.rt[p], 1, n, x, y) << '\n'; } else { int p, k; cin >> p >> k; if (k > TRE.Dat(TRE.rt[p])) cout << "-1\n"; else cout << TRE.kth(TRE.rt[p], 1, n, k) << '\n'; } } return 0; } ```