[bzoj3123][洛谷P3302] [SDOI2013]森林（树上主席树+倍增lca+启发式合并）

本文主要是介绍[bzoj3123][洛谷P3302] [SDOI2013]森林（树上主席树+倍增lca+启发式合并），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门(luogu)
传送门(bzoj)
此题有两种操作：
1.查询树上两点间权值第k小
2.连接两棵树
限制条件：强制在线
看到第k小大家想到的肯定是主席树，可是连边又让大家想到了LCT
我们选择使用主席树。
为什么呢？
我们肯定是要舍弃两种操作中的一种，让它变慢，另一个就快了。
然而，第k小显然没有什么优化的余地，可是连接两棵树显然就是合并两棵树
合并！我们可以想到启发式合并！它可以优化合并到 $O(logn)$ ，一个log的消耗还是可以承受的。
于是具体实现就是，我们可以记录每棵树的大小，合并的时候把小的接到大的上面去，合并的时候我们dfs暴力修改，用父节点重建每个节点的主席树，并且更新每个节点的倍增数组（st表）。
更新倍增数组这里还是有技巧的，我们不需要dfs完了才修改，我们可以一边dfs一边改：

void dfs(int x,int father,int rt){//这一段st[x][0]=father;for(int k=1;k<=16;k++){st[x][k]=st[st[x][k-1]][k-1];}//上面son[rt]++;dep[x]=dep[father]+1;fa[x]=father;vis[x]=1;insert(root[x],root[father],1,size,Hash(a[x]));for(int i=head[x];i;i=e[i].next){int u=e[i].to;if(u==father)continue;dfs(u,x,rt);}
}

这就是如何合并。
然后我们来讨论查询。
主席树大家肯定都写过，但是大部分人写的都是针对数组的，这里我们要在树上建主席树。
每一颗主席树维护的是它到根节点的数字信息，于是类似于原本的主席树，我们可以发现每一个节点和它的父亲节点维护的主席树没有太大的变化，最多只会变化logn个点，于是我们dfs时可以利用每个节点的父亲的主席树来建立它的主席树。
查询时怎么做呢？
我们可以记录四个变量，从四个节点同时查询
假设查询节点分别是 $x,y$ ，那它们分别就是： $x,y,lca(x,y),father(lca(x,y))$
每次主席树操作时，就是这样：

int query(int x,int y,int pre1,int pre2,int l,int r,int k){if(l==r)return b[l];int lsize=t[t[x].ls].size+t[t[y].ls].size-t[t[pre1].ls].size-t[t[pre2].ls].size;int mid=(l+r)>>1;if(k<=lsize)return query(t[x].ls,t[y].ls,t[pre1].ls,t[pre2].ls,l,mid,k);else return query(t[x].rs,t[y].rs,t[pre1].rs,t[pre2].rs,mid+1,r,k-lsize);
}

建树和原来一样：

void insert(int &now,int pre,int l,int r,int x){now=++cnt;t[now]=t[pre];t[now].size++;if(l==r)return;int mid=(l+r)>>1;if(x<=mid)insert(t[now].ls,t[pre].ls,l,mid,x);else insert(t[now].rs,t[pre].rs,mid+1,r,x);
}

每个根节点还要先build一下：

void build(int &now,int l,int r){now=++cnt;t[now].size=0;if(l==r)return;int mid=(l+r)>>1;build(t[now].ls,l,mid);build(t[now].rs,mid+1,r);
}

剩下的倍增lca的我就不说了。
还有就是这个题需要离散化，也很正常。
还有就是一个坑点，那个testcase是编号！不是组数！我被这个坑到10分。。。
剩下就是尽量优化优化常数，常数不要太大。
还要开够空间。
代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#define ll long long
using namespace std;
inline int read(){int x=0;char ch=' ';int f=1;while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();if(ch=='-')f=-1,ch=getchar();while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;
}
struct edge{int to,next;
}e[320001];
int T,n,m,q,tot;
int a[80001];
int fa[80001];
int son[80001];
int head[80001];
inline void addedge(int x,int y){e[++tot].to=y;e[tot].next=head[x];head[x]=tot;
}
struct Node{int size,ls,rs;
}t[80001*600];
int cnt;
int root[80001];
void build(int &now,int l,int r){now=++cnt;t[now].size=0;if(l==r)return;int mid=(l+r)>>1;build(t[now].ls,l,mid);build(t[now].rs,mid+1,r);
}
void insert(int &now,int pre,int l,int r,int x){now=++cnt;t[now]=t[pre];t[now].size++;if(l==r)return;int mid=(l+r)>>1;if(x<=mid)insert(t[now].ls,t[pre].ls,l,mid,x);else insert(t[now].rs,t[pre].rs,mid+1,r,x);
}
int b[80001];
int size;
int query(int x,int y,int pre1,int pre2,int l,int r,int k){if(l==r)return b[l];int lsize=t[t[x].ls].size+t[t[y].ls].size-t[t[pre1].ls].size-t[t[pre2].ls].size;int mid=(l+r)>>1;if(k<=lsize)return query(t[x].ls,t[y].ls,t[pre1].ls,t[pre2].ls,l,mid,k);else return query(t[x].rs,t[y].rs,t[pre1].rs,t[pre2].rs,mid+1,r,k-lsize);
}
inline int Hash(int x){return lower_bound(b+1,b+size+1,x)-b;
}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);
}
int st[80001][17];
int dep[80001];
int vis[80001];
void dfs(int x,int father,int rt){st[x][0]=father;for(int k=1;k<=16;k++){st[x][k]=st[st[x][k-1]][k-1];}son[rt]++;dep[x]=dep[father]+1;fa[x]=father;vis[x]=1;insert(root[x],root[father],1,size,Hash(a[x]));for(int i=head[x];i;i=e[i].next){int u=e[i].to;if(u==father)continue;dfs(u,x,rt);}
}
inline int getlca(int x,int y){if(x==y)return x;if(dep[x]>dep[y])swap(x,y);for(int k=16;k>=0;k--){if(dep[st[y][k]]>=dep[x]){y=st[y][k];}}if(x==y)return x;for(int k=16;k>=0;k--){if(st[x][k]!=st[y][k]){x=st[x][k];y=st[y][k];}}return st[x][0];
}
int main(){T=read();T=1;while(T--){memset(head,0,sizeof(head));memset(dep,0,sizeof(dep));memset(vis,0,sizeof(vis));memset(st,0,sizeof(st));memset(son,0,sizeof(son));tot=0;cnt=0;n=read();m=read();q=read();for(int i=1;i<=n;i++){a[i]=read();b[i]=a[i];fa[i]=i;}sort(b+1,b+n+1);size=unique(b+1,b+n+1)-b-1;for(int i=1;i<=m;i++){int x=read(),y=read();addedge(x,y);addedge(y,x);}build(root[0],1,size);for(int i=1;i<=n;i++){if(!vis[i]){dfs(i,0,i);fa[i]=i;}}int lastans=0;for(int i=1;i<=q;i++){char ch[3];int x,y,k;scanf("%s",ch);x=read()^lastans;y=read()^lastans;if(ch[0]=='Q'){k=read()^lastans;int lca=getlca(x,y);lastans=query(root[x],root[y],root[lca],root[st[lca][0]],1,size,k);printf("%d\n",lastans);}else{addedge(x,y);addedge(y,x);int u=find(x);int v=find(y);if(son[u]<son[v]){swap(u,v);swap(x,y);}dfs(y,x,u);}}}return 0;
}