yukicoder : No.1641 Tree Xor Query

これは割と典型か。
https://yukicoder.me/problems/no/1641

問題

根付き木が与えられる。
各頂点vには整数値C[v]が設定されている。

以下のクエリに答えよ。

• 頂点vの値をC[v] = C[v] xor yで更新する
• 頂点vに対し、vのSubTree内の全頂点wにおけるC[w]全部のxorを答える

解法

先に頂点をDFS訪問順で並べ替えておくと、後者のクエリは数列の区間に対するxorとすることができる。
そこでBITを使い区間のxorを高速で計算できるようにすればよい。

int N,Q;

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s^=bit[e-1],e-=e&-e; return s;}
	void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]^=v,e+=e&-e;}
};
BIT<int,20> bt;

int C[101010];
int id;
int L[101010],R[101010];
vector<int> E[101010];

void dfs(int cur,int pre) {
	L[cur]=id++;
	bt.add(L[cur]+1,C[cur]);
	FORR(e,E[cur]) if(e!=pre) dfs(e,cur);
	R[cur]=id;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N) cin>>C[i];
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	dfs(0,0);
	
	FOR(i,Q) {
		cin>>j>>x>>y;
		x--;
		if(j==1) {
			bt.add(L[x]+1,y);
		}
		else {
			cout<<(bt(R[x])^bt(L[x]))<<endl;
		}
	}
	
	
}

まとめ

だいぶ追い付いてきたな。