感觉可持久化 trie 最多就是用在异或和上了吧.
- #include<bits/stdc++.h>
- #define N
- #define INF 2100000001
- using namespace std;
- int read()
- {
- int x=0,f=1;char s=getchar();
- while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
- while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
- return x*f;
- }
- int go[600005*23][3],root[600005],latest[600005*23],a[600005];
- int tot=0;
- void insert(int i,int k,int p,int q)
- {
- if(k<0){latest[q]=i;return;}
- int c=a[i]>>k&1;
- if(p)go[q][c^1]=go[p][c^1];// 除了字符指针 si 不同之外, 节点 q 和节点 p 的其他信息完全相同
- go[q][c]=++tot;
- insert(i,k-1,go[p][c],go[q][c]);
- latest[q]=max(latest[go[q][0]],latest[go[q][1]]);//latest 表示在可持久化 trie 中以 q 为根的子树中结尾标记的最大 (最晚的可以到达此点的 trie)
- // 满足大于 l-1 就行了
- }
- int query(int q,int val,int k,int lim)
- {
- if(k<0) return a[latest[q]]^val;
- int c=val>>k&1;
- if(latest[go[q][c^1]]>=lim)return query(go[q][c^1],val,k-1,lim);
- else return query(go[q][c],val,k-1,lim);
- }
- char op[2];
- int main()
- {
- int n=read(),m=read();
- latest[0]=-1;
- for(int i=1;i<=n;++i)
- {
- a[i]=read();
- a[i]=a[i]^a[i-1];// 存前缀和
- root[i]=++tot;
- insert(i,23,root[i-1],root[i]);// 不会超过 2^23
- }
- for(int i=1;i<=m;++i)
- {
- scanf("%s",&op);
- if(op[0]=='A')
- {
- int x=read();
- ++n;
- a[n]=x;
- a[n]=a[n]^a[n-1];
- root[n]=++tot;
- insert(n,23,root[n-1],root[n]);
- }
- else
- {
- int l=read(),r=read(),x=read();
- printf("%d\n",query(root[r-1],a[n]^x,23,l-1));//r-1 和 l-1, 因为要消去前面的前缀异或和 (a^a=0)
- }
- }
- }
- View Code
来源: http://www.bubuko.com/infodetail-3131334.html