Codeforces 817E Choosing The Commander 0/1字典树

66 阅读 0 评论 44 点赞

我是靠谱客的博主落寞香菇，最近开发中收集的这篇文章主要介绍Codeforces 817E Choosing The Commander 0/1字典树，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意：有三种操作，在一个集合中

（1）加入1个数（2）删除1个数（3）询问 p,l 这个集合中有多少个数满足 x^p<l

解：

考虑 L的二进制下的每一位

1.如果是1那么就x^p有希望直接比这一位小，那么直接加上小的这部分的数量

否则向大小相等的方向向下探索

2.如果是0的话，x这一位怎么选都不会比它小，所以向相等的方向探索

#include<bits/stdc++.h>
#define en 'n'
#define ll long long
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn = 1e5+5;
const int maxm=maxn*60;
int rd()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x;
}
int cnt[maxm],tr[maxm][2];
int tot=1;
void add(int x){
    int v=1;
    for(int i=30;i>=0;--i){
        int t=((x>>i)&1);
        if(tr[v][t]==0)
        tr[v][t]=++tot;
        v=tr[v][t];
        cnt[v]+=1;
    }
}
void del(int x){
int v=1;
for(int i=30;i>=0;--i){
    int t=((x>>i)&1);
    v=tr[v][t];
    cnt[v]-=1;
}
}
int ask(int p,int l){
    int v=1;
    int res=0;
    for(int i=30;i>=0;--i){
        int tem=((l>>i)&1);
        int temp=(p>>i)&1;
        if(tem){
                res+=cnt[tr[v][temp]];
                v=tr[v][temp^1];
        }
        else{
         v=tr[v][temp];
        }
    }
    return res;
}
signed main()
{
    #ifdef local
    freopen("input2.txt","r",stdin);
    #endif
    #define int register int
    int q=rd();
    for(int i=1;i<=q;i++){
        int op=rd();
        if(op==1){
            int tem=rd();add(tem);
        }else if(op==2){
            int tem=rd();del(tem);
        }
        else
        {
            int p=rd(),l=rd();
            cout<<ask(p,l)<<en;
        }
    }
    return 0;
}