【BZOJ 4103】 [Thu Summer Camp 2015]異或運算 可持久化01Trie

我們觀察數據：樹套樹 PASS ? ?主席樹 PASS ?一層一個Trie PASS

再看，異或！我們就把目光暫時定在01Tire然后我們發現，我們可以帶著一堆點在01Trie上行走，因為O(n*q*30+m*30)是一個可選復雜度。

我們想一下我們正常的時候的01Trie其實是通過在每一層比較大小來確定這一為是0還是1，所以我們從上到下一位一位地走，統計每在這一位異或值為1的數的個數，如果這一位是一的個數大于k那么我們就使這一位為1，那么我們就舍棄這一位為0的狀態就是所有的點都走變為1的路，如果這一位是一的個數小于k那么我們就使這一位為0，其余同理。

#include <cstdio>
using namespace std;
const int A=30,MAXN=12000000,N=1010,M=300010;
inline void read(int &sum){register char ch=getchar();for(sum=0;ch<'0'||ch>'9';ch=getchar());for(;ch>='0'&&ch<='9';sum=(sum<<1)+(sum<<3)+ch-'0',ch=getchar());
}
struct Trie{Trie *ch[2];int size;
}*root[M],*null,node[MAXN],*now[N][2];
int n,m,sz=1,a[N];
int main(){null=node,null->ch[0]=null->ch[1]=null,root[0]=null;read(n),read(m);for(register int i=1;i<=n;i++)read(a[i]);for(register int i=1,x;i<=m;i++){read(x),root[i]=node+sz,sz++;register Trie *p=root[i],*last=root[i-1];for(register int i=A;i>=0;i--)p->ch[(x>>i)&1]=node+sz,sz++,p->ch[((x>>i)&1)^1]=last->ch[((x>>i)&1)^1],p=p->ch[(x>>i)&1],last=last->ch[(x>>i)&1],p->size=last->size+1;}register int u,d,l,r,k,Q;read(Q);while(Q--){read(u),read(d),read(l),read(r),read(k);register int ret=0;for(register int i=u;i<=d;i++)now[i][1]=root[r],now[i][0]=root[l-1];for(register int i=A,sum=0;i>=0;i--,sum=0){for(register int j=u;j<=d;j++)sum+=((a[j]>>i)&1)==0?(now[j][1]->ch[1]->size-now[j][0]->ch[1]->size):(now[j][1]->ch[0]->size-now[j][0]->ch[0]->size);if(sum>=k){ret|=1<<i;for(register int j=u;j<=d;j++)now[j][1]=now[j][1]->ch[((a[j]>>i)&1)^1],now[j][0]=now[j][0]->ch[((a[j]>>i)&1)^1];}else{k-=sum;for(register int j=u;j<=d;j++)now[j][1]=now[j][1]->ch[(a[j]>>i)&1],now[j][0]=now[j][0]->ch[(a[j]>>i)&1];}}printf("%d\n",ret);}return 0;
}

?