提出 #74871997

---

ソースコード 拡げる

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define sz(x) (int)(x).size()
using namespace std;
typedef long long ll;
template<typename Node, typename F> struct SegTree {
    int n, size;
    Node e; // 항등원
    vector<Node> tree;
    F func;
    SegTree(int n, const Node& e, F func) : n(n), size(1<<(__lg(n)+1)), e(e), tree(size<<1, e), func(func) {}
    SegTree(const vector<Node>& v, const Node& e, F func) : n(sz(v)), size(1<<(__lg(n)+1)), e(e), tree(size<<1, e), func(func) {
        for (int i = 0; i < n; i++) tree[i+size] = v[i];
        for (int i = size-1; i > 0; i--) tree[i] = func(tree[i<<1], tree[i<<1 | 1]);
    }
    void update(int i, const Node& val) {
        tree[i += size] = val;
        while (i >>= 1) {
            tree[i] = func(tree[i<<1], tree[i<<1 | 1]);
        }
    }
    Node query(int i) { return tree[i + size]; }
    Node query(int l, int r) {
        Node L = e, R = e;
        for (l += size, r += size; l <= r; l >>= 1, r >>= 1) {
            if (l & 1) L = func(L, tree[l++]);
            if (~r & 1) R = func(tree[r--], R);
        }
        return func(L, R);
    }
};
int main() {
    fastio; int N, M, Q; cin >> N >> M >> Q;
    vector<int> ver(N+1); int vc = 0;
    vector<vector<array<int,3>>> adj(Q+1), qv(Q+1);
    int q = 0;
    for (int i = 0; i < Q; i++) {
        int a, x, y; cin >> a >> x >> y;
        if (a == 1) {
            ver[x] = ver[y];
        }
        else if (a == 2) {
            int z; cin >> z;
            adj[ver[x]].push_back({ ++vc, y, z });
            ver[x] = vc;
        }
        else {
            int z; cin >> z;
            qv[ver[x]].push_back({ q++, y, z });
        }
    }
    vector<ll> ans(q);
    SegTree sg(M, (ll)0, [](ll a, ll b) { return a+b; });
    auto dfs = [&](auto dfs, int u) -> void {
        for (auto [id, l, r] : qv[u]) {
            ans[id] = sg.query(l, r);
        }
        for (auto [v, y, z] : adj[u]) {
            ll t = sg.query(y);
            sg.update(y, z);
            dfs(dfs, v);
            sg.update(y, t);
        }
    };
    dfs(dfs, 0);
    for (auto i : ans) cout << i << "\n";
    return 0;
}

提出情報

ジャッジ結果