結果

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

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

vector <int> adj[100001];
long long int tree[300001];
long long int lazy[300001];
int L[100001];
int R[100001];
int arr[100001];

void dfs(int now,int prev,int &num)
{
	L[now] = ++num;
	for(auto next : adj[now])
	{
		if(prev==next)
		{
			continue;
		}
		dfs(next,now,num);
	}
	R[now] = num;
}

void propagate(int node,int start,int end)
{
	if(lazy[node]>0)
	{
		if((end-start+1)%2)
		{
			tree[node]^=lazy[node];
		}
		if(start!=end)
		{
			lazy[node*2]^=lazy[node];
			lazy[node*2+1]^=lazy[node];
		}
		lazy[node]=0;
	}
	return;
}

long long int update(int node,int start,int end,int left,int right,int value)
{
	propagate(node,start,end);

	if(left>end || right<start)
	{
		return tree[node];
	}

	if(left<=start && end<=right)
	{
		if((end-start+1)%2)
		{
			tree[node]^=value;
		}
		
		if(start!=end)
		{
			lazy[node*2]^=value;
			lazy[node*2+1]^=value;
		}
		
		//propagate(node,start,end);
		return tree[node];
	}

	int mid = (start+end)/2;

	tree[node] = update(node*2,start,mid,left,right,value)^update(node*2+1,mid+1,end,left,right,value);
	return tree[node];
}

long long int Xor(int node,int start,int end,int left,int right)
{
	propagate(node,start,end);

	if(left>end || right<start)
	{
		return 0;
	}

	if(left<=start && end<=right)
	{
		return tree[node];
	}

	int mid = (start+end)/2;

	return Xor(node*2,start,mid,left,right)^Xor(node*2+1,mid+1,end,left,right);
}


int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	int n, m;
	
	cin >> n >> m;

	for(int i=1;i<=n;i++)
	{
		cin >> arr[i];
	}
	
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}


	int num = 0;
	dfs(1,0,num);

	for(int i=1;i<=n;i++)
	{
		update(1,1,n,L[i],L[i],arr[i]);
	}
	for(int i=0;i<m;i++)
	{
		int x,y,z;
		cin >> x;
		if(x==1)
		{
			cin >> y >> z;
			update(1,1,n,L[y],L[y],z);
		}
		else
		{
			cin >> y >> z;
			cout << Xor(1,1,n,L[y],R[y]) << '\n';
		}
	}

	return 0;
}
0