题目链接:Choosing The Commander
维护一个带删除的Trie,然后每次在Trie中找即可。
分别讨论一下。
AC代码:
#pragma GCC optimize("-Ofast","-funroll-all-loops")#include<bits/stdc++.h>//#define int long longusing namespace std;const int N=1e5+10;int t[N*30][2],idx,cnt[N*30],q;inline void insert(int x,int v){int p=0;for(int i=26;i>=0;i--){int k=x>>i&1;if(!t[p][k])t[p][k]=++idx;p=t[p][k];cnt[p]+=v;}}int ask(int x,int y){int p=0,res=0;for(int i=26;i>=0;i--){if(y>>i&1){if(x>>i&1)res+=cnt[t[p][1]],p=t[p][0];elseres+=cnt[t[p][0]],p=t[p][1];}else{if(x>>i&1)p=t[p][1];elsep=t[p][0];}if(!cnt[p])break;}return res;}signed main(){cin>>q;for(int i=1,op,p,l;i<=q;i++){scanf("%d %d",&op,&p);if(op==1)insert(p,1);else if(op==2)insert(p,-1);else scanf("%d",&l),printf("%d\n",ask(p,l));}return 0;}