結果
問題 | No.1641 Tree Xor Query |
ユーザー |
![]() |
提出日時 | 2021-10-11 16:29:46 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 112 ms / 5,000 ms |
コード長 | 4,757 bytes |
コンパイル時間 | 3,075 ms |
コンパイル使用メモリ | 218,820 KB |
最終ジャッジ日時 | 2025-01-25 00:06:51 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 18 |
ソースコード
#pragma GCC optimize("Ofast")#include <bits/stdc++.h>#define rep(i,n) for(int i=0;i<n;i++)#define cinf(n,x) for(int i=0;i<(n);i++)cin>>x[i];#define ft first#define sc second#define pb push_back#define lb lower_bound#define ub upper_bound#define all(v) (v).begin(),(v).end()#define LB(a,x) lb(all(a),x)-a.begin()#define UB(a,x) ub(all(a),x)-a.begin()#define mod 1000000007//#define mod 998244353#define FS fixed<<setprecision(15)using namespace std;typedef long long ll;const double pi=3.141592653589793;template<class T> using V=vector<T>;using P=pair<ll,ll>;typedef unsigned long long ull;typedef long double ldouble;template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }template<class T> inline void out(T a){ cout << a << '\n'; }void YN(bool ok){if(ok) cout << "Yes" << endl; else cout << "No" << endl;}//void YN(bool ok){if(ok) cout << "YES" << endl; else cout << "NO" << endl;}const ll INF=1e18;const int mx=200005;//abc222//Segtree templateclass Segtree{public:ll N=1;V<ll> dat;explicit Segtree(ll sz){while(N<sz) N*=2;dat.reserve(2*N+3);rep(i,2*N+3)dat[i]=0;}ll get(int i){return dat[i+N];}// Range Minimum Query -------------------------void min_init(){for(int i=0;i<N;i++)min_update(i,INF);}void min_update(ll k,ll a){k+=N;dat[k]=a;while(k>1){k=k/2;dat[k]=min(dat[2*k],dat[2*k+1]);}}ll get_min(int l,int r){ll res=INF;l=l+N;r=r+N;while(l<r){if(l&1) res=min(res,dat[l++]);if(r&1) res=min(res,dat[--r]);l >>= 1;r >>= 1;}return res;}//Range Maximum Query ---------------------------void max_init(){for(int i=0;i<N;i++)max_update(i,-INF);}void max_update(ll k,ll a){k+=N;dat[k]=a;while(k>1){k/=2;dat[k]=max(dat[2*k],dat[2*k+1]);}}ll get_max(ll l,ll r){ll res=-INF;l=l+N;r=r+N;while(l<r){if(l&1) res=max(res,dat[l++]);if(r&1) res=max(res,dat[--r]);l >>= 1;r >>= 1;}return res;}//Range Sum Query -----------------------------void sum_update(ll k,ll a){k+=N;dat[k]+=a;while(k>1){k/=2;dat[k]=(dat[2*k]+dat[2*k+1]);}}ll get_sum(ll l,ll r){ll res=0;l+=N;r+=N;while(l<r){if(l&1) res=(res+dat[l++]);if(r&1) res=(res+dat[--r]);l >>= 1;r >>= 1;}return res;}ll kth(ll k){ll cur=1;ll S=0;while(cur*2<=2*N-1){if(S+dat[2*cur]>=k){cur=2*cur;}else{S+=dat[2*cur];cur=2*cur+1;}}cur-=N;return cur;}//その他----------------------------------------ll unit(){return 0LL;//単位元}ll calc(ll a,ll b){return (a^b);//演算}void update(ll k,ll a){k+=N;dat[k]^=a;while(k>1){k/=2;dat[k]=calc(dat[2*k],dat[2*k+1]);}}ll get_val(ll l,ll r){ll res=unit();l=l+N;r=r+N;while(l<r){if(l&1) res=calc(res,dat[l++]);if(r&1) res=calc(res,dat[--r]);l >>= 1;r >>= 1;}return res;}};int main(){//オーバーフローは大丈夫ですか??cin.tie(0);ios::sync_with_stdio(false);int n,qq;cin>>n >>qq;V<ll> c(n);cinf(n,c);V<V<int>> G(n);rep(i,n-1){int a,b;cin>>a>>b;a--;b--;G[a].pb(b);G[b].pb(a);}V<int> iki(n),kaeri(n);int cnt=0;function<void(int,int)> dfs=[&](int p,int v){iki[v]=cnt++;for(int u:G[v]){if(u==p) continue;dfs(v,u);}kaeri[v]=cnt;};dfs(-1,0);Segtree seg(cnt);rep(i,n){int id=iki[i];seg.update(id,c[i]);}while(qq--){int t;ll x,y;cin>>t>>x>>y;x--;if(t==1){int id=iki[x];seg.update(id,y);}else{int l=iki[x];int r=kaeri[x];out(seg.get_val(l,r));}}}