给一个可重集
1.插入
2.删除
3.询问 p[i] xor p[j]<l[j] 的个数
考虑01tire
构造一个p[i] xor p[j]<=l[j]
x=p[i] xor p[j]
计算贡献
1.l[j]这一位是1,构造x这一位也是1,计算构造x这一位为0的情况个数,递归下去
2.l[j]这一位是0,构造x这一位也是0,递归下去
// Problem: E. Choosing The Commander
// Contest: Codeforces - Educational Codeforces Round 23
// URL: https://codeforces.com/problemset/problem/817/E
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<iostream>
#include<algorithm>
#include<vector>
#define INF (1ll<<60)
using namespace std;
typedef long long ll;
const int N=1e5+9;
const int M=31;
struct trie{
int ch[N*M][2],cur=1,val[N*M],c[N*M];
void insert(ll x){
int u=1;
for(int i=M;i>=0;i--){
int t=(x>>i)&1ll;
if(!ch[u][t]){
ch[u][t]=++cur;
}
u=ch[u][t];
c[u]++;
}
val[u]=x;
}
void erase(ll x){
int u=1;
for(int i=M;i>=0;i--){
int t=(x>>i)&1ll;
u=ch[u][t];
c[u]--;
}
}
ll query(ll x,ll y){
ll res=0;
int u=1;
for(int i=M;i>=0;i--){
int t=(x>>i)&1ll,tt=(y>>i)&1ll;
if(tt){//是1
res+=c[ch[u][t]];//计算贡献 t^t=0,0<1
u=ch[u][t^1];//构造x<=l
}else{
u=ch[u][t];//构造x<=l
}
}
return res;
}
}st;
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int q;
cin>>q;
for(int i=1;i<=q;i++){
int op;
cin>>op;
if(op==1){
int p;
cin>>p;
st.insert(p);
}else if(op==2){
int p;
cin>>p;
st.erase(p);
}else{
int p,l;
cin>>p>>l;
cout<<st.query(p,l)<<'\n';
}
}
return 0;
}