結果

問題 No.1641 Tree Xor Query
ユーザー snrnsidysnrnsidy
提出日時 2021-08-10 21:32:32
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 134 ms / 5,000 ms
コード長 1,976 bytes
コンパイル時間 2,225 ms
コンパイル使用メモリ 204,724 KB
実行使用メモリ 20,424 KB
最終ジャッジ日時 2023-10-24 06:20:01
合計ジャッジ時間 4,717 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
9,132 KB
testcase_01 AC 4 ms
9,132 KB
testcase_02 AC 3 ms
9,080 KB
testcase_03 AC 4 ms
9,140 KB
testcase_04 AC 3 ms
9,140 KB
testcase_05 AC 4 ms
9,140 KB
testcase_06 AC 4 ms
9,140 KB
testcase_07 AC 3 ms
9,140 KB
testcase_08 AC 3 ms
9,136 KB
testcase_09 AC 4 ms
9,140 KB
testcase_10 AC 3 ms
9,140 KB
testcase_11 AC 4 ms
9,140 KB
testcase_12 AC 4 ms
9,140 KB
testcase_13 AC 134 ms
20,424 KB
testcase_14 AC 132 ms
20,424 KB
testcase_15 AC 6 ms
9,352 KB
testcase_16 AC 12 ms
9,748 KB
testcase_17 AC 8 ms
9,460 KB
testcase_18 AC 9 ms
9,576 KB
testcase_19 AC 6 ms
9,192 KB
testcase_20 AC 103 ms
14,192 KB
権限があれば一括ダウンロードができます

ソースコード

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