CodeChef CookOff 2014 March XOR Minimization

CodeChef データ構造

問題

長さNの配列があり、次のようなクエリが来るので処理せよ。
1 l r : {a[i]|l≦i≦r}の最小値を求める。
2 l r x : l≦i≦rなるiについて、a[i] = a[i] ^ xとする。^はbitwise xor

制約条件

N≦250000
0≦a[i], x≦65535

方針

セグメント木を使おうとしたけど更新が上手くできなかった。
平方分割だと階層がないので上手くできた。


平方分割で、各バケットごとにTrie木と、その区間全体にかかっているxorを持つ。
Trie木にはそのバケットが担当する配列を2進法であらわした文字列について、それぞれ個数を入れておく。


で、最小値の求め方。
区間にすっぽり収まっているバケットについては、
Trieを使って最小値を求める。xorで1が立っているビットは1を優先して、立ってないビットは0を優先してTrie木を辿ろうとすれば、最小値がわかる。


区間にすっぽり収まっていないバケットについては、直接計算する。


更新の仕方は以下の通り。
区間にすっぽり収まっているバケットについては、xor値だけを更新する。
バケットからはみ出ている要素は、その要素の値を直接書き換える。
それとともにTrie木も更新する。


計算量は、O(Q * sqrt(N) * log(A))とか。

ソースコード

#define F first
#define S second

const int N = 250000;
const int M = 500;

int child[N*16*10][2], value[N*16*10], trie_sz = 1;
inline int node(){
	assert(trie_sz + 1 < N*16*10);
	return trie_sz++;
}

int n, q, a[N];
int root[M], sum[M];
pi mn[M];

inline void add(int &r, int v, int x, int pos = 15){
	if(!r) r = node();
	value[r] += x;
	if(pos < 0) return;
	
	add(child[r][v >> pos & 1], v, x, pos - 1);
}
inline pi get(int r, int s, int ans = 0, int pos = 15){
	if(pos < 0) return mp(ans, value[r]);
	rep(ii, 2){
		int i = ii ^ (s >> pos & 1);
		if(child[r][i] && value[child[r][i]]) return get(child[r][i], s, ans * 2 + ii, pos - 1);
	}
	assert(0);
}

int main(){
	
	scanf("%d%d", &n, &q);
	rep(i, n) scanf("%d", a + i);
	
	rep(i, M) mn[i] = mp(inf, 0);
	rep(i, n){
		add(root[i / M], a[i], 1);
		if(mn[i / M].F > a[i]) mn[i / M] = mp(a[i], 0);
		if(mn[i / M].F == a[i]) mn[i / M].S++;
	}
	//rep(i, n) cerr<<mn[i/M].F<<" "<<mn[i/M].S<<" : "<<i<<endl;
	
	while(q--){
		int type, l, r, x;
		scanf("%d%d%d", &type, &l, &r);
		l--;
		
		if(type == 1){
			pi ans = mp(inf, 0);
			while(l % M && l < r){
				if(ans.F > (a[l] ^ sum[l / M])) ans = mp(a[l] ^ sum[l / M], 0);
				if(ans.F == (a[l] ^ sum[l / M])) ans.S++;
				l++;
			}
			while(r % M && l < r){
				r--;
				if(ans.F > (a[r] ^ sum[r / M])) ans = mp(a[r] ^ sum[r / M], 0);
				if(ans.F == (a[r] ^ sum[r / M])) ans.S++;
			}
			l /= M; r /= M;
			while(l < r){
				if(ans.F > mn[l].F) ans = mp(mn[l].F, 0);
				if(ans.F == mn[l].F) ans.S += mn[l].S;
				l++;
			}
			
			printf("%d %d\n", ans.F, ans.S);
		}
		else{
			scanf("%d", &x);
			while(l % M && l < r){
				add(root[l / M], a[l], -1); a[l] ^= x;
				add(root[l / M], a[l], 1);
				l++;
				
				if(l % M == 0) mn[l / M - 1] = get(root[l / M - 1], sum[l / M - 1]);
			}
			while(r % M && l < r){
				r--;
				add(root[r / M], a[r], -1); a[r] ^= x;
				add(root[r / M], a[r], 1);
				
				if(r % M == 0) mn[r / M] = get(root[r / M], sum[r / M]);
			}
			l /= M; r /= M;
			while(l < r){
				sum[l] ^= x;
				mn[l] = get(root[l], sum[l]);
				l++;
			}
		}
	}
	
	return 0;
}