結果

問題 No.1641 Tree Xor Query
ユーザー nononnonon
提出日時 2024-09-27 11:41:57
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 102 ms / 5,000 ms
コード長 7,033 bytes
コンパイル時間 3,778 ms
コンパイル使用メモリ 266,576 KB
実行使用メモリ 33,152 KB
最終ジャッジ日時 2024-09-27 11:42:25
合計ジャッジ時間 5,130 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 2 ms
6,944 KB
testcase_07 AC 2 ms
6,944 KB
testcase_08 AC 2 ms
6,944 KB
testcase_09 AC 2 ms
6,940 KB
testcase_10 AC 2 ms
6,940 KB
testcase_11 AC 2 ms
6,940 KB
testcase_12 AC 2 ms
6,940 KB
testcase_13 AC 101 ms
33,024 KB
testcase_14 AC 102 ms
33,152 KB
testcase_15 AC 4 ms
6,944 KB
testcase_16 AC 8 ms
6,944 KB
testcase_17 AC 6 ms
6,944 KB
testcase_18 AC 6 ms
6,944 KB
testcase_19 AC 4 ms
6,944 KB
testcase_20 AC 67 ms
14,564 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

template <typename Monoid>
struct segtree {
    using S = typename Monoid::S;
    segtree() : segtree(0) {}
    segtree(int _n) : segtree(vector<S>(_n, Monoid::e())) {}
    segtree(const vector<S> &v) : n(v.size()) {
        log = 1;
        while ((1 << log) < n) log++;
        sz = 1 << log;
        d = vector<S>(2 * sz, Monoid::e());
        for (int i = 0; i < n; i++) d[i + sz] = v[i];
        for (int i = sz - 1; i >= 1; i--) update(i);
    }
    void set(int p, const S &x) {
        assert(0 <= p && p < n);
        p += sz;
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }
    S get(int p) const {
        assert(0 <= p && p < n);
        return d[p + sz];
    }
    S prod(int l, int r) const {
        assert(0 <= l && l <= r && r <= n);
        l += sz;
        r += sz;
        S pl = Monoid::e(), pr = Monoid::e();
        while (l < r) {
            if (l & 1) pl = Monoid::op(pl, d[l++]);
            if (r & 1) pr = Monoid::op(d[--r], pr);
            l >>= 1;
            r >>= 1;
        }
        return Monoid::op(pl, pr);
    }
    S all_prod() const { return d[1]; }
private:
    int n, log, sz;
    vector<S> d;
    void update(int p) {
        d[p] = Monoid::op(d[2 * p], d[2 * p + 1]);
    }
};

template<typename Monoid>
struct heavy_light_decomposition {
    using S = typename Monoid::S;
    heavy_light_decomposition(int _n, bool _e, int _r = 0) : n(_n), root(_r), edge(_e), built(false) { edges.reserve(n); }
    void add_edge(int u, int v, S w = Monoid::e()) {
        assert(0 <= u && u < n);
        assert(0 <= v && v < n);
        assert(!built);
        edges.emplace_back(u, v, w);
    }
    vector<S> rearrange(const vector<S> &a = {}) {
        build();
        vector<S> res(n);
        if (edge) {
            assert(a.empty());
            for (auto [u, v, w] : edges) {
                if (in[u] > in[v]) swap(u, v);
                res[in[v]] = w;
            }
        } else {
            assert(int(a.size()) == n);
            for (int u = 0; u < n; u++) {
                res[in[u]] = a[u];
            }
        }
        return res;
    }
    template<typename L>
    void vertex_set(int u, const S &x, const L &set) {
        assert(0 <= u && u < n);
        build();
        set(in[u], x);
    }
    template<typename L>
    void edge_set(int u, int v, const S &x, const L &set) {
        assert(edge);
        assert(0 <= u && u < n);
        assert(0 <= v && v < n);
        build();
        if (in[u] > in[v]) swap(u, v);
        set(in[v], x);
    }
    template<typename L>
    void edge_set(int i, const S &x, const L &set) {
        assert(0 <= i && i < n - 1);
        build();
        auto &[u, v, w] = edges[i];
        w = x;
        edge_set(u, v, x, set);
    }
    template<typename F, typename L>
    void path_apply(int u, int v, const F &f, const L &apply) {
        assert(0 <= u && u < n);
        assert(0 <= v && v < n);
        build();
        int hu = head[u], hv = head[v];
        while (hu != hv) {
            if (in[hu] > in[hv]) {
                swap(u, v);
                swap(hu, hv);
            }
            apply(in[hu], in[v] + 1, f);
            v = par[v];
            hu = head[u];
            hv = head[v];
        }
        if (in[u] > in[v]) swap(u, v);
        apply(in[u] + edge, in[v] + 1, f);
    }
    template<typename F, typename L>
    void subtree_apply(int u, const F &f, const L &apply) {
        assert(0 <= u && u < n);
        build();
        apply(in[u] + edge, out[u], f);
    }
    template<typename L, typename R>
    S path_prod(int u, int v, const L &prod, const R &rev) {
        assert(0 <= u && u < n);
        assert(0 <= v && v < n);
        bool flip = false;
        S pu = Monoid::e(), pv = Monoid::e();
        int hu = head[u], hv = head[v];
        while (hu != hv) {
            if (in[hu] > in[hv]) {
                swap(u, v);
                swap(hu, hv);
                swap(pu, pv);
                flip = !flip;
            }
            S p = prod(in[hv], in[v] + 1);
            pv = Monoid::op(p, pv);
            v = par[hv];
            hu = head[u];
            hv = head[v];
        }
        if (in[u] > in[v]) {
            swap(u, v);
            swap(pu, pv);
            flip = !flip;
        }
        S p = prod(in[u] + edge, in[v] + 1);
        pv = Monoid::op(p, pv);
        pv = Monoid::op(rev(pu), pv);
        return flip ? rev(pv) : pv;
    }
    template<typename L>
    S path_prod(int u, int v, const L &prod) {
        return path_prod(u, v, prod, [&](const S &x) { return x; });
    }
    template<typename L>
    S subtree_prod(int u, const L &prod) {
        assert(0 <= u && u < n);
        build();
        return prod(in[u] + edge, out[u]);
    }
private:
    int n, root, id;
    vector<vector<int>> g;
    bool edge, built;
    vector<int> sub, depth, par, in, out, head, heavy;
    vector<tuple<int, int, S>> edges;
    void dfs(int u, int p) {
        par[u] = p;
        sub[u] = 1;
        int sub_max = 0;
        for (int v : g[u]) {
            if (v != p) {
                dfs(v, u);
                sub[u] += sub[v];
                if (sub[v] > sub_max) {
                    sub_max = sub[v];
                    heavy[u] = v;
                }
            }
        }
    }
    void decompose(int u, int h) {
        head[u] = h;
        in[u] = id++;
        if (heavy[u] != -1) decompose(heavy[u], h);
        for (int v : g[u]) {
            if (v != heavy[u] && v != par[u]) {
                decompose(v, v);
            }
        }
        out[u] = id;
    }
    void build() {
        if (built) return;
        g.resize(n);
        sub.resize(n);
        depth.resize(n);
        par.resize(n, -1);
        in.resize(n);
        out.resize(n);
        head.resize(n);
        heavy.resize(n, -1);
        for (const auto &[u, v, w] : edges) {
            g[u].push_back(v);
            g[v].push_back(u);
        }
        id = 0;
        dfs(root, root);
        decompose(root, root);
        built = true;
    }
};

struct Monoid {
    using S = int;
    static S op(S a, S b) { return a ^ b; }
    static S e() { return 0; }
};

int main () {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, Q;
    cin >> N >> Q;
    vector<int> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    heavy_light_decomposition<Monoid> G(N, false);
    for (int i = 1; i < N; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        G.add_edge(u, v);
    }
    segtree<Monoid> seg(G.rearrange(A));
    auto update = [&](int p, int x) -> void {
        int y = seg.get(p);
        seg.set(p, x ^ y);
    };
    auto prod = [&](int l, int r) -> int {
        return seg.prod(l, r);
    };
    while (Q--) {
        int t, x, y;
        cin >> t >> x >> y;
        if (t == 1) {
            x--;
            G.vertex_set(x, y, update);
        } else {
            x--;
            cout << G.subtree_prod(x, prod) << '\n';
        }
    }
}
0