結果

問題 No.1641 Tree Xor Query
ユーザー srjywrdnprktsrjywrdnprkt
提出日時 2023-10-21 15:58:47
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 302 ms / 5,000 ms
コード長 2,617 bytes
コンパイル時間 2,083 ms
コンパイル使用メモリ 211,828 KB
実行使用メモリ 26,996 KB
最終ジャッジ日時 2023-10-21 15:58:52
合計ジャッジ時間 4,638 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 1 ms
4,348 KB
testcase_02 AC 2 ms
4,348 KB
testcase_03 AC 2 ms
4,348 KB
testcase_04 AC 1 ms
4,348 KB
testcase_05 AC 2 ms
4,348 KB
testcase_06 AC 2 ms
4,348 KB
testcase_07 AC 2 ms
4,348 KB
testcase_08 AC 2 ms
4,348 KB
testcase_09 AC 2 ms
4,348 KB
testcase_10 AC 2 ms
4,348 KB
testcase_11 AC 2 ms
4,348 KB
testcase_12 AC 1 ms
4,348 KB
testcase_13 AC 291 ms
26,996 KB
testcase_14 AC 302 ms
26,996 KB
testcase_15 AC 5 ms
4,348 KB
testcase_16 AC 16 ms
4,644 KB
testcase_17 AC 11 ms
4,348 KB
testcase_18 AC 11 ms
4,492 KB
testcase_19 AC 8 ms
4,348 KB
testcase_20 AC 184 ms
16,848 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

template<class S, S (*op)(S, S), S (*e)()>struct SegTree {
    private:
        vector<S> seg; int N = 1;
        S _prod (int l, int r, int idx, int bitl, int bitr) const{
            if (r < bitl || l > bitr) return e();
            if (l <= bitl && bitr <= r) return seg[idx];

            ll bitm = (bitl+bitr)/2;
            return op(_prod(l, r, idx*2+1, bitl, bitm), _prod(l, r, idx*2+2, bitm+1, bitr));
        }

    public:
        SegTree (ll n) : SegTree(vector<S>(n, e())) {}
        SegTree (const vector<S> &v){
            ll n = v.size(); while (N < n) N *= 2; seg.resize(N*2-1, e());
            for (ll i=0; i<n; i++) seg[i+N-1] = v[i];
            for (ll i=N-2; i>=0; i--) seg[i] = op(seg[i*2+1], seg[i*2+2]);
        }
        void set(int loc, S val){
            loc += N-1; seg[loc] = val;
            while (loc != 0) loc = (loc-1)/2, seg[loc] = op(seg[loc*2+1], seg[loc*2+2]);
        }
        S prod (int l, int r) const {return _prod(l, r, 0, 0, N-1);}
        S all_prod() const {return seg[0];}
        S get (int i) const{return seg[i+N-1];}
        void show() const{
            for (int i=N-1; i<N*2-1; i++) cout << seg[i] << " ";
            cout << endl;
        }
};

ll op(ll a, ll b){ return a ^ b;}
ll e(){ return 0;}

int main(){
 
    ll N, Q, a, b, t;
    cin >> N >> Q;
    vector<ll> C(N);
    for (int i=0; i<N; i++) cin >> C[i];
    vector<vector<ll>> E(N);
    for (int i=0; i<N-1; i++){
        cin >> a >> b; a--; b--;
        E[a].push_back(b);
        E[b].push_back(a);
    }

    //in...頂点xに入ったのは何ステップ目か？
    //out...頂点xから出たのは何ステップ目か？
    //tour...i番目に訪れた頂点のxor(帰りは0)
    vector<int> in(N), out(N);
    vector<ll> tour;
    auto euler_tour=[&](auto self, int from, int p)->void{
        in[from] = tour.size();
        tour.push_back(C[from]);
        for(auto to : E[from]){
            if (p == to) continue;
            self(self, to, from);
        }
        out[from] = tour.size();
        tour.push_back(0);
    };
    euler_tour(euler_tour, 0, -1);
    /*
    for (int i=0; i<N; i++) cout << in[i] << " ";
    cout << endl;
    for (int i=0; i<N; i++) cout << out[i] << " ";
    cout << endl;
    for (auto x : tour) cout << x << " ";
    cout << endl;
    */

    SegTree<ll, op, e> tree(tour);
 
    while(Q){
        Q--;
        cin >> t >> a >> b; a--;
        if (t == 1) tree.set(in[a], tree.get(in[a]) ^ b);
        else cout << tree.prod(in[a], out[a]) << endl;
    }
 
    return 0;
}
0