【BZOJ3123】[Sdoi2013]森林

Description

【BZOJ3123】[Sdoi2013]森林主席树+倍增LCA+启发式合并-LMLPHP

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。之后的操作类似。
【BZOJ3123】[Sdoi2013]森林主席树+倍增LCA+启发式合并-LMLPHP

题解：跟BZOJ2588差不多，只不过变成了森林，所以采用启发式合并，每次将小的树暴力重构，塞到大的树里就行了。

话说这题并不需要并查集，只需要记录一下每个点的树根和这棵树的大小就行了

RE的注意！：

1.testcase是测试点编号！好好读题！所以这东西没有卵用
2.每次重构的时候不要这样写

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

    fa[x][i]=fa[fa[x][i-1]][i-1];

因为原先x的深度可能比重构后的深度要大，所以以前的某些fa值在重构后并没有清掉，导致搜LCA时出错，进而WA->RE

所以必须这样写

for(i=1;i<20;i++)

    fa[x][i]=fa[fa[x][i-1]][i-1];

这一个错误害我调了一个上午~

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int maxn=80010;

int n,m,nm,cnt,T,tot,lastans;

int to[maxn<<1],next[maxn<<1],head[maxn],v[maxn],fa[maxn][20],dep[maxn],root[maxn],siz[maxn];

int Log[maxn],rt[maxn],ref[maxn];

struct sag

{

	int siz,ls,rs;

}s[maxn*300];

struct node

{

	int v,org;

}num[maxn];

char str[10];

bool cmp(node a,node b)

{

	return a.v<b.v;

}

int rd()

{

	int ret=0,f=1;	char gc=getchar();

	while(gc<'0'||gc>'9')	{if(gc=='-')f=-f;	gc=getchar();}

	while(gc>='0'&&gc<='9')	ret=ret*10+gc-'0',gc=getchar();

	return ret*f;

}

void add(int a,int b)

{

	to[cnt]=b,next[cnt]=head[a],head[a]=cnt++;

}

void insert(int x,int &y,int l,int r,int pos)

{

	if(pos>r)	return ;

	y=++tot;

	if(l==r)

	{

		s[y].siz=s[x].siz+1;

		return ;

	}

	int mid=l+r>>1;

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

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

	s[y].siz=s[s[y].ls].siz+s[s[y].rs].siz;

}

int query(int a,int b,int c,int d,int l,int r,int k)

{

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

	int mid=l+r>>1,sm=s[s[a].ls].siz+s[s[b].ls].siz-s[s[c].ls].siz-s[s[d].ls].siz;

	if(sm>=k)	return query(s[a].ls,s[b].ls,s[c].ls,s[d].ls,l,mid,k);

	else	return query(s[a].rs,s[b].rs,s[c].rs,s[d].rs,mid+1,r,k-sm);

}

void dfs(int x)

{

	siz[root[x]]++;

	int i;

	for(i=1;i<20;i++)	fa[x][i]=fa[fa[x][i-1]][i-1];

	insert(rt[fa[x][0]],rt[x],1,nm,v[x]);

	for(i=head[x];i!=-1;i=next[i])

		if(to[i]!=fa[x][0])

			fa[to[i]][0]=x,dep[to[i]]=dep[x]+1,root[to[i]]=root[x],dfs(to[i]);

}

int main()

{

	rd();

	n=rd(),m=rd(),T=rd();

	int i,j,a,b,c,d;

	memset(head,-1,sizeof(head));

	for(i=2;i<=n;i++)	Log[i]=Log[i>>1]+1;

	for(i=1;i<=n;i++)	num[i].v=rd(),num[i].org=i;

	sort(num+1,num+n+1,cmp);

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

	{

		if(num[i].v>ref[nm])	ref[++nm]=num[i].v;

		v[num[i].org]=nm;

	}

	for(i=1;i<=m;i++)	a=rd(),b=rd(),add(a,b),add(b,a);

	for(i=1;i<=n;i++)	if(!root[i])	root[i]=i,dfs(i);

	for(i=1;i<=T;i++)

	{

		scanf("%s",str),a=rd()^lastans,b=rd()^lastans;

		if(str[0]=='L')

		{

			if(siz[root[a]]>siz[root[b]])	swap(a,b);

			fa[a][0]=b,dep[a]=dep[b]+1,root[a]=root[b],add(a,b),add(b,a),dfs(a);

		}

		else

		{

			c=a,d=b;

			if(dep[a]<dep[b])	swap(a,b);

			for(j=Log[dep[a]-dep[b]];j>=0;j--)	if(dep[a]-(1<<j)>=dep[b])	a=fa[a][j];

			if(a!=b)

			{

				for(j=Log[dep[a]];j>=0;j--)

					if(fa[a][j]!=fa[b][j])	a=fa[a][j],b=fa[b][j];

				a=fa[a][0];

			}

			b=rd()^lastans;

			lastans=query(rt[c],rt[d],rt[a],rt[fa[a][0]],1,nm,b);

			printf("%d\n",lastans);

		}

	}

	return 0;

}

森林