結果

問題 No.1641 Tree Xor Query
ユーザー ゆきのん
提出日時 2021-08-06 23:10:24
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 316 ms / 5,000 ms
コード長 2,936 bytes
コンパイル時間 2,097 ms
コンパイル使用メモリ 203,680 KB
最終ジャッジ日時 2025-01-23 16:10:33
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
//#include<atcoder/all>
//#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
//using namespace atcoder;
//using namespace boost::multiprecision;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long ll;
typedef pair<ll,ll> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a,T b){return b?gcd(b,a%b):a;}
const ll mod=1e9 + 7;
const ll LINF=1ll<<60;
const int INF=1<<30;
//int dx[]={0,1,0,-1,0,1,-1,1,-1};
//int dy[]={0,0,1,0,-1,1,-1,-1,1};
int dx[]={0,0,1,-1};
int dy[]={-1,1,0,0};

vector<vector<int>> g(1<<17); //グラフの隣接リスト
vector<int> v; //オイラーツアーの頂点配列
vector<int> ind(1<<17), out(1<<17); //各頂点がオイラーツアー配列の何番目に最初に訪れるか

void dfs(int now, int par){//今の頂点、親の頂点
    ind[now] = v.size();
    v.push_back(now);
    for(int i = 0; i < g[now].size(); i++){
        if(g[now][i] != par){
            dfs(g[now][i],now);
            v.push_back(now);
        }
    }
    out[now] = v.size();
}

template <typename T>
struct SegmentTree{
    using F = function<T(T,T)>;
    int n;
    F f;
    T ti;
    vector<T> dat;
    SegmentTree(){};
    SegmentTree(F f,T ti):f(f),ti(ti){}
    void init(int n_){    
        n=1;
        while(n<n_) n<<=1;
        dat.assign(n<<1,ti);
    }
    void build(const vector<T> &v){
        int n_=v.size();
        init(n_);
        for(int i=0;i<n_;i++) dat[n+i]=v[i];
        for(int i=n-1;i;i--)
            dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]);
    }
    void set_val(int k,T x){
        dat[k+=n]=x;
        while(k>>=1)
            dat[k]=f(dat[(k<<1)|0],dat[(k<<1)|1]);    
    }
    T query(int a,int b){
        T vl=ti,vr=ti;
        for(int l=a+n,r=b+n;l<r;l>>=1,r>>=1) {
            if(l&1) vl=f(vl,dat[l++]);
            if(r&1) vr=f(dat[--r],vr);
        }
        return f(vl,vr);
    }
};



int main(){
    int n,q;cin >> n >> q;
    vector<ll> c(n);
    for (int i = 0; i < n; i++) {
        cin >> c[i];
    }
    for (int i = 0; i < n-1; i++) {
        int x,y;cin >> x >> y;
        x--,y--;
        g[x].pb(y);
        g[y].pb(x);
    }
    dfs(0, 0);
    SegmentTree<ll> seg([](ll a, ll b){
        return a ^ b;
    }, 0ll);
    seg.build(vector<ll> (2 * n, 0));
    for (int i = 0; i < n; i++) {
        seg.set_val(ind[i], c[i]);
    }
    
    while(q--){
        int t,x,y;cin >> t >> x >> y;
        x--;
        if(t == 1){
            ll t = seg.query(ind[x], ind[x] + 1);
            seg.set_val(ind[x], t ^ y);
        }
        else{
            cout << seg.query(ind[x], out[x] + 1) << endl;
        }
    }
    return 0;
}
0