Educational Codeforces Round 23：E. Choosing The Commander（字典树01异或）

题意：
3种操作：

1 插入一个数

2 删除一个数

3 给出一个数pi和l，询问有多少个数pj满足pi^pj<l

思路：
建字典树，询问的时候当碰到 l 的某一位为1的某一位为1的时候，就更新结果，然后继续搜索
注意siz初始化为1

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e6+5;
int t,tire[maxn][2],sp[40],lp[40],p[40],siz=1,val[maxn];
void insert(int* s,int w){
int now=1;
for(int i=0;i<=28;i++){
if(!tire[now][s[i]])tire[now][s[i]]=++siz;
now=tire[now][s[i]];
val[now]+=w;
}
}
int query(int* s,int* l){
int now=1,ans=0;
for(int i=0;i<=28;i++){
if(l[i])ans+=val[tire[now][s[i]]];
now=tire[now][s[i]^l[i]];
}
return ans;
}
void getbit(int x){
for(int i=28,d=1<<i,z=0;i>=0;i--,d=1<<i,z++){
if(x&d)p[z]=1;
else p[z]=0;
}
}
int main(){
scanf("%d",&t);
while(t--){
int op,a,b;
scanf("%d",&op);
if(op==1){
scanf("%d",&a);
getbit(a);
for(int i=0;i<=28;i++)sp[i]=p[i];
insert(sp,1);
}
else if(op==2){
scanf("%d",&a);
getbit(a);
for(int i=0;i<=28;i++)sp[i]=p[i];
insert(sp,-1);
}
else{
scanf("%d%d",&a,&b);
getbit(a);
for(int i=0;i<=28;i++)sp[i]=p[i];
getbit(b);
for(int i=0;i<=28;i++)lp[i]=p[i];
printf("%dn",query(sp,lp));
}
}
}

最后

以上就是冷静自行车为你收集整理的Educational Codeforces Round 23：E. Choosing The Commander（字典树01异或）Educational Codeforces Round 23：E. Choosing The Commander（字典树01异或）的全部内容，希望文章能够帮你解决Educational Codeforces Round 23：E. Choosing The Commander（字典树01异或）Educational Codeforces Round 23：E. Choosing The Commander（字典树01异或）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。