提出 #74880123

---

ソースコード 拡げる

#include <bits/stdc++.h>
#define endl '\n'

using namespace std;
using i64 = long long;

struct PersistentSegTree {
    struct Node {
        i64 sum;
        int l, r;
    };

    int n, tot;
    vector<Node> tr;

    PersistentSegTree() {}
    PersistentSegTree(int n, int maxNode) {
        init(n, maxNode);
    }

    void init(int _n, int maxNode) {
        n = _n;
        tot = 0;
        tr.assign(maxNode + 1, {0, 0, 0});
    }

    int clone(int p) {
        tr[++tot] = tr[p];
        return tot;
    }

    int modify(int p, int l, int r, int pos, int val) {
        int u = clone(p);
        if (l == r) {
            tr[u].sum = val;
            return u;
        }

        int mid = (l + r) >> 1;
        if (pos <= mid) {
            tr[u].l = modify(tr[p].l, l, mid, pos, val);
        } else {
            tr[u].r = modify(tr[p].r, mid + 1, r, pos, val);
        }

        tr[u].sum = tr[tr[u].l].sum + tr[tr[u].r].sum;
        return u;
    }

    i64 query(int p, int l, int r, int ql, int qr) {
        if (!p) {
            return 0;
        }
        if (ql <= l && r <= qr) {
            return tr[p].sum;
        }

        int mid = (l + r) >> 1;
        i64 res = 0;
        if (ql <= mid) {
            res += query(tr[p].l, l, mid, ql, qr);
        }
        if (qr > mid) {
            res += query(tr[p].r, mid + 1, r, ql, qr);
        }
        return res;
    }

    int modify(int root, int pos, int val) {
        return modify(root, 1, n, pos, val);
    }

    i64 query(int root, int l, int r) {
        return query(root, 1, n, l, r);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m, q;
    cin >> n >> m >> q;

    PersistentSegTree seg(m, (q + 5) * 25);

    vector<int> root(n + 1, 0);

    while (q--) {
        int op;
        cin >> op;

        if (op == 1) {
            int x, y;
            cin >> x >> y;
            root[x] = root[y];
        } else if (op == 2) {
            int x, y, z;
            cin >> x >> y >> z;
            root[x] = seg.modify(root[x], y, z);
        } else {
            int x, l, r;
            cin >> x >> l >> r;
            cout << seg.query(root[x], l, r) << endl;
        }
    }

    return 0;
}

提出情報

ジャッジ結果