Choosing The Commander

Problem - 817E - Codeforces

给一个可重集

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;
}