結果

問題 No.1641 Tree Xor Query
コンテスト
ユーザー riano
提出日時 2021-08-06 22:19:34
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 265 ms / 5,000 ms
コード長 2,952 bytes
コンパイル時間 1,928 ms
コンパイル使用メモリ 177,104 KB
実行使用メモリ 22,128 KB
最終ジャッジ日時 2024-09-17 02:23:19
合計ジャッジ時間 3,633 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define Pr pair<ll,ll>
#define Tp tuple<ll,ll,ll>
using Graph = vector<vector<int>>;
#define double long double

const ll mod = 1000000007;


//dfs
//s:始点 i:dfs回数 t:始点からの距離
vector<int> vis; int t;
vector<int> depth;
//探索範囲を距離L以下に制限する場合
int L;
vector<ll> l(100001),r(100001);
void dfs(Graph &G, int s,int i){
    t++;
    l[s] = t;
    for(int nx:G[s]){
        if(t>=L) break;
        if(vis[nx]==i) continue;
        depth[nx] = depth[s] + 1;
        vis[nx] = i;
        dfs(G,nx,i);
    }
    t++;
    r[s] = t;
}


//segment tree
//1-indexed all
class segtree {
public:
    ll n;
    vector<ll> A;
    segtree(ll k){
        n = 1;
        while(n<k){ n *= 2; }
        A=vector<ll>(2*n,0);
    }

    //a[i]にxを加算する
    void add(ll i,ll x){
        int index = n-1+i;
        A[index] ^= x;
        while(index>1){
            index /= 2;
            A[index] = A[2*index]^A[2*index+1];
        }
    }

    //a[i]をにする
    void replace(ll i,ll x){
        int index = n-1+i;
        A[index] = x;
        while(index>1){
            index /= 2;
            A[index] = A[2*index]^A[2*index+1];
        }
    }

    //a[i]+a[i+1]+…+a[j]を求める
    ll sum(ll i,ll j){
        return rangesum(i,j,1,1,n);
    }

    // a,b求める区間 k区間番号 c,d区間の始終点(k=1,c=1,d=nで入力する)
    ll rangesum(ll a,ll b,ll k,ll c,ll d){
        //単位元の設定
        ll el = 0;
        if(d<a||b<c){
            return el;
        }
        else if(a<=c&&d<=b){
            return A[k];
        }
        else{
            //2区間に分割して演算を行う
            ll p = rangesum(a,b,k*2,c,(c+d)/2)^rangesum(a,b,k*2+1,(c+d)/2+1,d);
            return p;
        }
    }

};

    
    

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    ll N,Q; cin >> N >> Q;
    Graph G(N+1);
    ll c[N+1];
    rep(i,N) cin >> c[i+1];
    rep(i,N-1){
        ll a,b; cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    //main関数内で
    vis.assign(N+1,-1);
    depth.assign(N+1,-1);
    int s = 1;
    vis[s] = 0; depth[s] = 0; t = 0; //s:始点
    L= 2000000000; //必要なら設定する
    dfs(G,s,0); //s:始点 i:dfs回数
    //main関数内で
    segtree seq(2*N+10);
    //などと宣言し  seq.replace(i,x);
    //のように使う 1-indexed 注意!!!!!!
    rep(i,N){
        seq.add(l[i+1],c[i+1]);
        // cout << l[i+1] << endl;
        // cout << seq.sum(l[i+1],l[i+1]) << endl;
    }
    rep(i,Q){
        ll t,x,y; cin >> t >> x >> y;
        if(t==1){
            seq.add(l[x],y);
            //cout << seq.sum(l[x],r[x]) << endl;
        }
        if(t==2){
            cout << seq.sum(l[x],r[x]) << endl;
        }
    }
    //cout << ans << endl;
}
0