题目大意： 总共有q次询问，对于每次询问有三种不同的操作； p = 1，增加一个数字 p = 2，去掉一个数字 p = 3，对于当前存在的数字，有x，s，问有多少 num[i]^x < s？
题解： 用字典树存所有的数字的二进制形式，sum存每种类型的个数，对于每次询问的复杂度都是log（n）。具体看代码。
代码：
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <stack> #include <bitset> #include <queue> #include <set> #include <map> #include <string> #include <algorithm> using namespace std; #define clr(a,b) memset(a,b,sizeof(a)) #define pb(a) push_back(a) #define fir first #define se second #define LL long long typedef pair<int,int> pii; typedef pair<LL,int> pli; typedef pair<LL,LL> pll; const int maxn = 1e5+5; const LL inf = 0x3f3f3f3f3f3f3f3f; LL mod = 1e9+7; double eps = 0.00000001; double PI = acos(-1); //用数组来模拟建树 struct BitTrie { int next[maxn*31][2],fa[maxn*31],sum[maxn*31],cnt; //next存下一个节点的下标，fa存父节点的下标，sum存当前节点的存在的所有数字个数，cnt即节点数 void init() { //初始化 cnt = 0; clr(next,-1); clr(sum,0); clr(fa,-1); } void add(int x,int cn) { int p = 0; for(int i = 31;i >= 0;i--) { int ff = (x>>i)&1; if(next[p][ff] == -1) { //如果没有就新建节点 next[p][ff] = ++cnt; } fa[next[p][ff]] = p; //保存父节点 p = next[p][ff]; //找到下一个节点 } sum[p] += cn; //for(int i = 0;i <= 10;i++) printf("%d ",fa[i]); //cout<<endl; while(p != -1) { //回溯把所有子节点的个数加到父节点 int nfa = fa[p]; sum[nfa] = 0; if(next[nfa][0] != -1) sum[nfa] += sum[next[nfa][0]]; if(next[nfa][1] != -1) sum[nfa] += sum[next[nfa][1]]; p = fa[p]; } } int query(int pp,int l) { int ans = 0,p = 0; for(int i = 31;i >= 0;i--) { int idp = (pp>>i)&1; int idl = (l>>i)&1; if(idl) { //如果位置i上l的二进制值是1，那么直接把二进制值是0的加到答案中，因为二进制值是0那么所有子节点都小于l，并且往下搜二进制值是1的子节点 if(next[p][idp] != -1) ans += sum[next[p][idp]]; if(next[p][!idp] != -1) p = next[p][!idp]; else break; } else { //如果位置i上l的二进制值是0，那么往下搜二进制值是0的子节点 if(next[p][idp] != -1) p = next[p][idp]; else break; } } return ans; } }; BitTrie tt; int main() { int q; cin>>q; tt.init(); while(q--) { int k,p,l; scanf("%d",&k); if(k == 1) { scanf("%d",&p); tt.add(p,1); } if(k == 2) { scanf("%d",&p); tt.add(p,-1); } if(k == 3) { scanf("%d%d",&p,&l); printf("%d\n",tt.query(p,l)); } } }入门了字典树吧，感觉字典树也不是很难。 come on！
