Codeforces Round #367 (Div. 2) D. Vasiliy's Multiset (TireTree之位字典树）-白红宇

Codeforces Round #367 (Div. 2) D. Vasiliy's Multiset (TireTree之位字典树）

阅读量：7090 次

发布时间：2019-06-28

本文共 1133 字，大约阅读时间需要 3 分钟。

题目链接：

题意：

对一个multiset（集合中的元素可以重复的set）有三种操作——

+ x: 增加元素x

- x: 减少元素x

？x: 求multiset中与x抑或得到的数最大为多少

已知0总是存在于multiset中。

分析：

时限为4s。

1 ≤ xi ≤ 10⁹,由于10⁹≈（2¹⁰）³≈2³⁰，10³<2¹⁰,也就是说x最多为30位

那么对数的每一位建立字典树，即最多为30层。

当要找与x抑或得到的结果最小的数时，只需尽可能找与x的每个数位相反的路径，

即可得到multiset中的那个数。

这样每个数都按照最大数可能的位数30来构建字典树，方便处理。

#include
      
       #include
       
        #include
        #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               using namespace std;typedef long long ll;const int mod = 1000000007;const int maxn = 200010;const int len = 30;struct node{ int cnt; int next[2];}tree[maxn*len];int num;void init(){ memset(tree,-1,sizeof(tree)); num = 0;}void add(int x){ int now = 0; bool k; for(int i=len-1;i>=0;i--) { k = (x>>i)&1; if(tree[now].next[k]==-1) tree[now].next[k] = ++num; now = tree[now].next[k]; tree[now].cnt = tree[now].cnt==-1?1:(tree[now].cnt+1); }}void del(int x){ int now = 0; bool k; for(int i=len-1;i>=0;i--) { k = (x&(1<
               
                =0;i--) { k = (x&(1<
                
                 0) k = !k; now = tree[now].next[k]; ret = ret|(k<