BZOJ_3123_[Sdoi2013]森林_主席树+启发式合并

2022-12-05 16:47:47

Description

Input

第一行包含一个正整数testcase，表示当前测试数据的测试点编号。保证1≤testcase≤20。
第二行包含三个整数N，M，T，分别表示节点数、初始边数、操作数。第三行包含N个非负整数表示 N个节点上的权值。
接下来 M行，每行包含两个整数x和 y，表示初始的时候，点x和点y 之间有一条无向边, 接下来 T行，每行描述一个操作，格式为“Q x y k”或者“L x y ”，其含义见题目描述部分。

Output

对于每一个第一类操作，输出一个非负整数表示答案。

Sample Input

1
8 4 8
1 1 2 2 3 3 4 4
4 7
1 8
2 4
2 1
Q 8 7 3 Q 3 5 1
Q 10 0 0
L 5 4
L 3 2 L 0 7
Q 9 2 5 Q 6 1 6

Sample Output

2
2
1
4
2

HINT

对于第一个操作 Q 8 7 3，此时 lastans=0，所以真实操作为Q 8^0 7^0 3^0，也即Q 8 7
3。点8到点7的路径上一共有5个点，其权值为4 1 1 2 4。这些权值中，第三小的为 2，输出 2，lastans变为2。对于第二个操作 Q 3
5 1 ，此时lastans=2，所以真实操作为Q 3^2 5^2 1^2 ，也即Q 1 7 3。点1到点7的路径上一共有4个点，其权值为 1
1 2 4 。这些权值中，第三小的为2，输出2，lastans变为 2。之后的操作类似。

考虑没有连边操作怎么做，直接树上主席树就可以。

发现没有删边操作，可以用一个实用的方法：启发式合并。

就是每次把小的那边暴力一个一个拆到大的那边。

实现起来还挺简单的。

代码：

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cstdlib>

#include <cmath>

using namespace std;

#define N 80050

int head[N],to[N<<1],nxt[N<<1],cnt,root[N],bl[N],f[20][N],Lg[N],n,m,val[N],V[N],dep[N],tot,vv;

int t[N*250],ls[N*250],rs[N*250],siz[N];

inline void add(int u,int v) {

	to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt;

}

void insert(int l,int r,int v,int &y,int x) {

	if(!y) y=++tot; t[y]=t[x]+1;

	if(l==r) return ;

	int mid=(l+r)>>1;

	if(v<=mid) rs[y]=rs[x],insert(l,mid,v,ls[y],ls[x]);

	else ls[y]=ls[x],insert(mid+1,r,v,rs[y],rs[x]);

}

int qk(int l,int r,int a,int b,int c,int d,int k) {

	if(l==r) return V[l];

	int mid=(l+r)>>1;

	int sizls=t[ls[a]]+t[ls[b]]-t[ls[c]]-t[ls[d]];

	if(k<=sizls) return qk(l,mid,ls[a],ls[b],ls[c],ls[d],k);

	else return qk(mid+1,r,rs[a],rs[b],rs[c],rs[d],k-sizls);

}

void dfs(int x,int y,int anc) {

	dep[x]=dep[y]+1;

	siz[anc]++;

	bl[x]=anc;

	f[0][x]=y;

	int i;

	insert(1,vv,val[x],root[x],root[y]);

	for(i=1;i<=19;i++) f[i][x]=f[i-1][f[i-1][x]];

	for(i=head[x];i;i=nxt[i]) {

		if(to[i]!=y) {

			dfs(to[i],x,anc);

		}

	}

}

int lca(int x,int y) {

	int i;

	if(dep[x]<dep[y]) swap(x,y);

	for(i=Lg[n];i>=0;i--) if(f[i][x]&&dep[f[i][x]]>=dep[y]) x=f[i][x];

	if(x==y) return x;

	for(i=Lg[n];i>=0;i--) if(f[i][x]&&f[i][x]!=f[i][y]) x=f[i][x],y=f[i][y];

	return f[0][x];

}

void solve() {

	// memset(t,0,sizeof(t));

	// memset(ls,0,sizeof(ls));

	// memset(rs,0,sizeof(rs));

	// memset(head,0,sizeof(head)); cnt=0;

	// memset(dep,0,sizeof(dep));

	int i;

	int Q;

	scanf("%d%d%d",&n,&m,&Q);

	for(Lg[0]=-1,i=1;i<=n;i++) Lg[i]=Lg[i>>1]+1;

	int x,y;

	for(i=1;i<=n;i++) scanf("%d",&val[i]),V[i]=val[i];

	sort(V+1,V+n+1);

	vv=unique(V+1,V+n+1)-V-1;

	for(i=1;i<=n;i++) val[i]=lower_bound(V+1,V+vv+1,val[i])-V;

	for(i=1;i<=m;i++) {

		scanf("%d%d",&x,&y); add(x,y); add(y,x);

	}

	for(i=1;i<=n;i++) {

		if(!f[0][i]) dfs(i,0,i);

	}

	int k,ans=0;

	char opt[3];

	while(Q--) {

		scanf("%s%d%d",opt,&x,&y);

		x^=ans; y^=ans;

		if(opt[0]=='Q') {

			scanf("%d",&k); k^=ans;

			int l=lca(x,y);

			// printf("%d\n",l);

			printf("%d\n",ans=qk(1,vv,root[x],root[y],root[l],root[f[0][l]]?root[f[0][l]]:0,k));

		}else {

			if(siz[bl[x]]>siz[bl[y]]) swap(x,y);

			f[0][x]=y; dep[x]=dep[y]+1;

			dfs(x,y,bl[y]); add(x,y); add(y,x);

		}

	}

}

int main() {

	scanf("%*d");

	solve();

}

/*

1

8 4 8

1 1 2 2 3 3 4 4

4 7

1 8

2 4

2 1

Q 8 7 3

Q 3 5 1

Q 10 0 0

L 5 4

L 3 2 L 0 7

Q 9 2 5

Q 6 1 6

*/

码农公寓