题解：P11209 『STA - R8』小熊游景点 II

## 分析
看到了 $\oplus$ 符号，基本上往 01Trie 上面去想是没有问题的。

一开始想到的是离线做法，由于 $b_i$ 都不相同，但是对于单个 $i$ 是相同的，所以把所有 $i$ 拆分开来，录入所有的 $k$，然后用 01Trie 计算答案。但是**本题部分测试点强制在线**打破了我所有念想。

之后推了一下，发现可以成对将 $a_i$ 和 $b_i$ 压入 01Trie，和我们学校之前的一场考试 T3 很像（当时数组开小加没开 ```long long``` 的双重 buf 保灵了）。

首先，设 $\forall k=0$，那么只考虑 $a_i$ 的贡献，且仅当存在一位 $d$，满足 $a_i$ 和 $b_i$ 前 $d-1$ 位均为 $0$，但是 $b_i$ 的第 $d$ 位为 $1$。

首先，考虑使用 $res_{root,bit}$ 表示这一组 $\{a_i,b_i\}$ 这一位下标为 $root$，$a_i$ 这一位为 $bit$，$b_i$ 这一位为 $1$ 的个数。在 ```insert``` 的时候不断加即可。

怎么 ```query``` 呢？每跳到一个 $root$，可以加上当前 $root$ 下的 $res_{root,bit}$，表示当前 $k$ 的这一位为 $bit$，需要往 $1$ 去加。到了最后，不要忘记加上 $end_{root}$，取等也可以。
## 坑点
- RE 这东西防不胜防，本人现在都没有搞明白 Trie 的保守数组大小，这一道题目应该是 $5\times 10^5\times 30$。
- ```query``` 函数内部要判断 ```root``` 归零的情况。
- ```end``` 变量名报错了，尽量用别的变量名代替。
- $T=0$ 的情况不用异或！我猜不会有人犯和我一样的错……
## 代码
```cpp
#include<bits/stdc++.h>
#define MAXN 500005
using namespace std;
int t,n,m,k,cnt=1,a[MAXN],b[MAXN],tree[MAXN*31][2],eof[MAXN*31],res[MAXN*31][2];
inline void insert(int a,int b){
	int root=1;
	for(int i=30;i>=0;--i){
		int x=a>>i&1,y=b>>i&1;
		if(y){
			++res[root][x];
		}
		if(!tree[root][x^y]){
			tree[root][x^y]=++cnt;
		}
		root=tree[root][x^y];
	}
	++eof[root];
}
inline int query(int a){
	int root=1,ans=0;
	for(int i=30;i>=0&&root;--i){
		int x=a>>i&1;
		ans+=res[root][x];
		root=tree[root][x];
	}
	return ans+eof[root];
}
int main(){
	scanf("%d %d %d",&t,&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=n;++i){
		scanf("%d",&b[i]);
		insert(a[i],b[i]);
	}
	int lastans=0;
	while(m--){
		scanf("%d",&k);
		if(t){
			k^=lastans;
		}
		printf("%d\n",lastans=query(k));
	}
	return 0;
}
```

正在渲染内容...