可持久化 $trie$ ....又是一个表里不一的东西.....
可持久化 $trie$ 的介绍：
和主席树类似的，其实可持久化就是体现在前缀信息的维护上（搞不懂这怎么就叫做可持久化了...）
$trie$ （字典树）大家应该都知道，就是一棵用来做字符串匹配的树，
但是！在这里，可持久化 $trie$ 就是完全不一样的东西了...
基本上（我做过的题），可持久化都是用来维护 $XOR$ 信息的...
比如说求某个范围内的最大区间异或和之类的，至于到了树上嘛，你懂的.
可持久化 $trie$ 的实现：
还是和主席树类似的，可持久化 $trie$ 就是要你在一棵树上（由于是异或，数字都会变成二进制，值只有 0 和 1 两种表示，于是这棵树自然就是二叉树了）维护每个前缀出现的次数（这里就是类似 trie 的做法）
哎...相信你是没有看懂的...于是边看代码边自己感性理解一下吧....
可持久化 $trie$ 的代码实现:
这其实是一道板子题的代码...
大体思路就是和主席树差不多，如果当前处理到了 0 ，那么 当前节点的 1 的孩子直接调用 las 所指向的孩子 1 就好了，
然后当前节点 和 las 节点都跳向 0 这个孩子，并且处理的这个过程是从高位到低位的（以符合查询时贪心的思想）
每次更新都是新增 30 （一般来说是这样，具体得看题目的数据范围） 个节点，所以不会炸
代码如下：
//by Judge
#include<iostream>
#include<cstdio>
using namespace std;
const int M=3e7+;
inline int read(){
int x=,f=; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-''; return x*f;
}
inline int cread(){
char c=getchar(); while(c!='Q' && c!='A') c=getchar(); return c^'Q';
}
int n,m,cnt;
int rt[M],son[M][],d[],sum[M];
inline void split(int k){
int i,len=;
while(k) d[++len]=k&,k>>=;
for(int i=len+;i<=;++i) d[i]=;
}
inline void update(int& now,int las){
sum[now=++cnt]=sum[las]+;
int i,tmp=now;
for(i=;i;--i){
son[tmp][d[i]^]=son[las][d[i]^],
son[tmp][d[i]]=++cnt,las=son[las][d[i]],
sum[tmp=cnt]=sum[las]+;
}
}
inline int query(int u,int v){
int ans=,i;
for(i=;i;--i){
if(sum[son[v][d[i]^]]-sum[son[u][d[i]^]]>)
ans|=(<<i-),u=son[u][d[i]^],v=son[v][d[i]^];
else u=son[u][d[i]],v=son[v][d[i]];
} return ans;
}
int main(){
int sum=,x,opt,l,r;
n=read(),m=read(),++n;
split(),update(rt[],rt[]);
for(int i=;i<=n;++i)
split(sum^=x=read()),
update(rt[i],rt[i-]);
for(int i=;i<=m;++i){
opt=cread();
if(opt)
split(sum^=x=read()),
update(rt[n+],rt[n]),++n;
else
l=read(),r=read(),x=read(),split(x^sum),
printf("%d\n",query(rt[l-],rt[r]));
} return ;
}
view code
可持久化 $trie$ 的例题：
其实上面已经是一道了。
然后这道（树上搞事情）的题：Tree
其实树上 可持久化 trie 和树上主席树类似，就是当前节点调用的 las 节点变成了该节点的父节点，查询的时候也是和树上主席树类似的套路，
这里和树上主席树一样是要查询 LCA 的，我们用树剖维护即可（而且还可以在树剖时维护每个节点的可持久化信息）
代码如下：
//by Judge
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int M=1e5+;
inline int read(){
int x=,f=; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-''; return x*f;
}
int n,m,pat,cnt;
int head[M],d[],rt[M],to[M<<][],sum[M<<];
int val[M],siz[M],dep[M],top[M],f[M],son[M];
struct Edge{
int to,next;
Edge(int to,int next): to(to),next(next){} Edge(){}
}e[M<<];
inline void add(int u,int v){
e[++pat]=Edge(v,head[u]),head[u]=pat;
e[++pat]=Edge(u,head[v]),head[v]=pat;
}
/************* 模板 ********************/
inline void split(int k){
int len=,i;
while(k) d[++len]=k&,k>>=;
for(i=len+;i<=;++i) d[i]=;
}
inline void update(int& root,int las){
int now=root=++cnt;
sum[now]=sum[las]+;
for(int i=;i;--i){
to[now][d[i]^]=to[las][d[i]^],
to[now][d[i]]=++cnt,las=to[las][d[i]],
now=cnt,sum[now]=sum[las]+;
}
}
#define v e[i].to
void dfs1(int u,int fa){
siz[u]=,son[u]=top[u]=;
split(val[u]),update(rt[u],rt[fa]);
for(int i=head[u];i;i=e[i].next) if(v!=fa){
f[v]=u,dep[v]=dep[u]+,dfs1(v,u),siz[u]+=siz[v];
if(siz[v]>siz[son[u]]) son[u]=v;
}
}
void dfs2(int u){
if(!top[u]) top[u]=u; if(!son[u]) return ;
top[son[u]]=top[u],dfs2(son[u]);
for(int i=head[u];i;i=e[i].next)
if(v!=son[u] && v!=f[u]) dfs2(v);
}
#undef v
inline int LCA(int u,int v){
while(top[u]^top[v])
dep[top[u]]>dep[top[v]]?u=f[top[u]]:v=f[top[v]];
return dep[u]<dep[v]?u:v;
}
/* 程序 */
inline int query(int u,int v,int lca,int f_lca){
int ans=;
for(int i=;i;--i){
if(sum[to[u][d[i]^]]+sum[to[v][d[i]^]]-sum[to[lca][d[i]^]]-sum[to[f_lca][d[i]^]])
ans|=(<<i-),u=to[u][d[i]^],v=to[v][d[i]^],lca=to[lca][d[i]^],f_lca=to[f_lca][d[i]^];
else u=to[u][d[i]],v=to[v][d[i]],lca=to[lca][d[i]],f_lca=to[f_lca][d[i]];
} return ans;
}
int x,y,z,lca;
inline void query(){
x=read(),y=read(),z=read(),lca=LCA(x,y),split(z);
printf("%d\n",query(rt[x],rt[y],rt[lca],rt[f[lca]]));
}
int main(){
while(~scanf("%d%d",&n,&m)){
pat=cnt=,memset(head,,sizeof(head));
for(int i=;i<=n;++i) val[i]=read();
for(int i=,u,v;i<n;++i)
u=read(),v=read(),add(u,v);
dfs1(,),dfs2(); while(m--) query();
} return ;
}
然后就是这题（TM做了我一晚上就在那里 TLE、 MLE 、WA 各种挂）： L
这道题...够恶心的，又是区间内询问区间...
而且更恶心的是，你要用分块的算法去优化算法...难以想到（其实打起来也还好）
$a[i]$ 代表 1 ~ i 的 前缀异或和
$f[i][j]$ 代表以第 i * block 这个位置开始，到 j-1 结束的区间内的前缀异或和中，与 a[j] 异或的最大值
代码如下：
//by Judge
#include<cmath>
#include<cstdio>
#include<iostream>
#define ll long long
using namespace std;
const int M=;
char buf[<<],*p1,*p2;
#define getchar() (p1==p2 && (p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
inline int read(){
int x=,f=; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-''; return x*f;
}
char sr[<<],z[];int C=-,Z;
inline void Ot(){fwrite(sr,,C+,stdout),C=-;}
inline void print(ll x){
if(C><<)Ot();if(x<)sr[++C]=,x=-x;
while(z[++Z]=x%+,x/=);
while(sr[++C]=z[Z],--Z);sr[++C]='\n';
}
int n,m,block,cnt,a[M<<],f[][M];
int d[],rt[M<<],to[M<<][],sum[M<<];
inline void split(int k){
int len=; while(k) d[++len]=k&,k>>=;
for(int i=len+;i<=;++i) d[i]=;
}
inline void update(int& root,int las){
int now=root=++cnt; sum[now]=sum[las]+;
for(int i=;i;--i){
to[now][d[i]^]=to[las][d[i]^];
to[now][d[i]]=++cnt,las=to[las][d[i]];
sum[now=cnt]=sum[las]+;
}
}
inline ll query(int u,int v){
ll ans=;
for(int i=;i;--i){
if(sum[to[v][d[i]^]]-sum[to[u][d[i]^]])
ans|=1ll<<i-,u=to[u][d[i]^],v=to[v][d[i]^];
else u=to[u][d[i]],v=to[v][d[i]];
} return ans;
}
int main(){
n=read(),m=read(),update(rt[],); int x,y,l,r,s,i,j; ll ans=;
for(i=;i<=n;++i) a[i]=read()^a[i-],split(a[i]),update(rt[i],rt[i-]);
for(block=(int)sqrt(n+)+,i=;i<=n;i+=block) for(j=i+;j<=n;++j)
split(a[j]),f[i/block][j]=max(1ll*f[i/block][j-],query(i?rt[i-]:,rt[j-]));
while(m--){
x=read(),y=read(),
r=max((1ll*x+ans)%n+,(1ll*y+ans)%n+),
s=l=min((1ll*x+ans)%n+,(1ll*y+ans)%n+)-;
while(s%block && s<r) ++s;
if(s==r){
for(ans=,j=l+;j<=r;++j)
split(a[j]),ans=max(ans,query(l?rt[l-]:,rt[j-]));
} else{
for(ans=f[s/block][r],j=s-;j>=l;--j)
split(a[j]),ans=max(ans,query(rt[j],rt[r]));
} print(ans);
} Ot(); return ;
}
其实这是一道省选题（已填坑）： Alo
题目说的就是要找出一个区间，让该区间内的次大值异或上区间内的任意一个数，使得异或和最大
坑... set 来维护已出现的下标，但是在使用 set 前居然要加入 -1、-2、inf、inf+1 四个元素...
以防止访问越界的情况（我们是依次枚举那个次大值，然后要找到前、后比他大的第二近的元素下标，也就是说容易越界）
然后这里还是要用到可（e）爱（xin）的前缀异或和
代码如下：
//by Judge
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<set>
using namespace std;
const int M=1e5+;
const int inf=1e9+;
char buf[<<],*p1,*p2;
#define getchar() (p1==p2 && (p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
inline int read(){
int x=,f=; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-''; return x*f;
}
int n,cnt,ans; set<int> q;
int d[],rt[M],sum[M<<],son[M<<][];
struct Node{ int id,val; }a[M];
inline bool operator <(Node& a,Node& b){
return a.val>b.val;
}
inline void split(int k){
int len=; while(k) d[++len]=k&,k>>=;
for(int i=len+;i<=;++i) d[i]=;
}
inline void update(int& nw,int las){
int now=nw=++cnt; sum[now]=sum[las]+;
for(int i=;i;--i){
son[now][d[i]^]=son[las][d[i]^];
son[now][d[i]]=++cnt,las=son[las][d[i]];
sum[now=cnt]=sum[las]+;
}
}
inline int query(int u,int v){
int ans=; for(int i=;i;--i){
if(sum[son[v][d[i]^]]-sum[son[u][d[i]^]])
ans|=(<<i-),u=son[u][d[i]^],v=son[v][d[i]^];
else u=son[u][d[i]],v=son[v][d[i]];
} return ans;
}
int main(){
n=read(); for(int i=;i<=n;++i) a[i].val=read(),a[i].id=i;
for(int i=;i<=n;++i) split(a[i].val),update(rt[i],rt[i-]);
q.insert(-),q.insert(inf),q.insert(-),q.insert(inf+),
sort(a+,a++n),q.insert(a[].id);
for(int i=;i<=n;++i){
int l=a[i].id,r=a[i].id,x=a[i].id;
set<int>::iterator t,p; t=p=q.lower_bound(x);
++t,r=*t-,--p,--p,l=*p+,l=max(,l),r=min(r,n),q.insert(x);
if(l^r) split(a[i].val),ans=max(ans,query(rt[l-],rt[r]));
} printf("%d\n",ans); return ;
}
这里用的就是set ，不过你手打 splay 也是没问题的
emmmmm...可持久化 trie 的题还是蛮少的...