数据结构压位trie P5312题解

Prean · 2022-01-06 15:54:05 · 题解

压位 T r i e 入门练习题（确信）

题意很清楚（

让我们先来想一想，如果没有排序操作的话，这道题应该怎么做。

我们维护一个 x 表示从开始到现在一共异或上了 x ，在序列末尾插入一个 n 相当于插入 n \bigoplus x 。

现在的问题就是：

询问 \sum_{i=l}^ra_i \bigoplus x
改变 x 。

位运算相关的还是考虑按位拆分比较好。

如果我们能够知道这个区间中的第 k 位有多少个 1 ，似乎就能够 O(k) 计算这一位对答案的贡献了。

于是我们使用一颗线段树来维护这个序列，每个位置开一个 \log V 的数组来维护这个东西，插入和询问的复杂度均为 O(\log n\log V) 。

那么我们加上排序操作？

众所周知 01trie 就是线段树，于是我们先把线段树改成 01trie。

我们发现异或上一个数可以看做将某几层的左儿子和右儿子交换。

然后在询问的时候搞清楚这一层有没有交换左右儿子，然后判断究竟该走哪边和该加上哪边就行了。

至于实现的话，对排序后的部分开一颗 01trie，未排序的部分直接使用前缀和统计。

时空复杂度都是 O((n+m)\log^2V) 。

然而你发现这样算下来大概是 660MB，会被卡空间。。。

如果我们能够将 01trie 的节点数量减少，那么我们就可以把空间压下来了。

所以我们将 01trie 改成压两位的压位 trie（也就是每个节点的度数为 4 ），空间就可以除以 2 了。

因为儿子个数并不是瓶颈，可以通过。

~~虽然说吧，你可以去赌 lxl 的插入操作很少，但是这明显还是会被卡（~~

以及细节巨多，需要判相同的数，~~还要判断我在什么时候异或上了多少。~~

#include<cstdio>
typedef unsigned ui;
const ui M=1e5+5,N=M*32;
ui n,m,cnt,k,tk,l1,l2,rt,ans[31],a[M<<1],S[M<<1][31];ui L,X[2];
struct Node{
    ui sz,chi[4],ans[31];
    inline ui&operator[](const ui&x){
        return chi[x];
    }
}t[N];
inline void swap(ui&a,ui&b){
    ui c=a;a=b;b=c;
}
ui Find(const ui&u,ui x,const ui&id=14){
    if(!u)return X[L++]=x,0;if(!~id)return X[L++]=x,0;const ui&k=tk>>(id<<1)&3;
    if(x<=t[t[u][0^k]].sz)return Find(t[u][0^k],x,id-1)|0<<(id<<1);x-=t[t[u][0^k]].sz;
    if(x<=t[t[u][1^k]].sz)return Find(t[u][1^k],x,id-1)|1<<(id<<1);x-=t[t[u][1^k]].sz;
    if(x<=t[t[u][2^k]].sz)return Find(t[u][2^k],x,id-1)|2<<(id<<1);x-=t[t[u][2^k]].sz;
    if(x<=t[t[u][3^k]].sz)return Find(t[u][3^k],x,id-1)|3<<(id<<1);x-=t[t[u][3^k]].sz;
}
void Qry(const ui&u,const ui&l,const ui&r,const ui&L=0,const ui&R=(1<<30)-1,const ui&id=14){
    if(!u||l>R||L>r)return;
    if(l<=L&&R<=r){
        for(ui i=0;i<=30;++i)ans[i]+=t[u].ans[i];return;
    }
    ui k=tk>>(id<<1)&3,m1,m2,m3;m2=L+R>>1;m1=L+m2>>1;m3=m2+1+R>>1;
    Qry(t[u][0^k],l,r,L,m1,id-1);Qry(t[u][1^k],l,r,m1+1,m2,id-1);
    Qry(t[u][2^k],l,r,m2+1,m3,id-1);Qry(t[u][3^k],l,r,m3+1,R,id-1);
}
void Insert(const ui&x){
    ui u=rt,id=14;
    while(~id){
        ++t[u].sz;for(ui i=0;i<=30;++i)if(x>>i&1)++t[u].ans[i];
        if(!t[u][x>>(id<<1)&3])t[u][x>>(id<<1)&3]=++cnt;u=t[u][x>>(id<<1)&3];--id;
    }
    ++t[u].sz;for(ui i=0;i<=30;++i)if(x>>i&1)++t[u].ans[i];
}
inline void ins(const ui&x,const ui&id){
    for(ui i=0;i<=30;++i)S[id][i]=S[id-1][i]+(x>>i&1);a[id]=x;
}
signed main(){
    ui i,x,l,r,q,p,opt;unsigned long long sum;scanf("%u",&n);rt=++cnt;
    for(i=1;i<=n;++i)scanf("%u",&x),ins(x,++l2);
    scanf("%u",&m);
    while(m--){
        scanf("%u",&opt);
        if(opt==1){
            scanf("%u",&x);ins(x^k,++l2);
        }
        if(opt==2){
            scanf("%u%u",&l,&r);for(i=0;i<=30;++i)ans[i]=0;sum=0;
            if(r<=l1){
                q=Find(rt,l);p=Find(rt,r);if(q^p)Qry(rt,q,p-1);--X[0];
                for(i=0;i<=30;++i)sum+=1ull*(k>>i&1?r-l+1+X[0]-X[1]-ans[i]:ans[i])<<i;
                sum+=1ull*(p^k^tk)*X[1];sum-=1ull*(q^k^tk)*X[0];
            }
            if(l<=l1&&l1<r){
                q=Find(rt,l);Qry(rt,q,(1<<30)-1);--X[0];
                for(i=0;i<=30;++i)sum+=1ull*(k>>i&1?l1-l+1+X[0]-ans[i]:ans[i])<<i;
                for(i=0;i<=30;++i)sum+=1ull*(k>>i&1?r-l1-S[r-l1][i]:S[r-l1][i])<<i;
                sum-=1ull*(q^k^tk)*X[0];
            }
            if(l1<l){
                r-=l1;l-=l1;
                for(i=0;i<=30;++i)sum+=1ull*(k>>i&1?r-l+1-(S[r][i]-S[l-1][i]):(S[r][i]-S[l-1][i]))<<i;
            }
            printf("%llu\n",sum);::L=0;
        }
        if(opt==3){
            scanf("%u",&x);k^=x;
        }
        if(opt==4){
            for(i=1;i<=l2;++i)Insert(a[i]);l1+=l2;tk=k;l2=0;
        }
    }
}

数据结构 压位trie P5312题解

数据结构压位trie P5312题解