NKOJ 2638 （SDOI 2013） 森林 （启发式LCA+主席树）

发表于 |
字数统计: 1,204字 | 阅读时长 ≈ 6min

P2638【SDOI2013 R1 Day1】森林

问题描述

这里写图片描述

输入格式

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

输出格式

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

样例输入

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

样例输出

2
2
1
4
2

注意观察，此题只有连接操作，而没有权值修改和删除操作，因此我们先考虑如果是一棵树的情况，那么显然用主席树维护，考虑主席树求第K小的时候，是两颗树相减，那么在树上只需要将每个节点都搞一棵主席树，等于他父亲那颗树加上他的权，那么就是x对应的树+y对应的树-LCA对应的树，然后加上LCA的单独点权即可。

那么考虑森林，因为只有连接操作，那么考虑暴力维护LCA，发现每次连接两颗树的时候，需要选一棵树来重新构建LCA，显然选点更少的一棵。可以证明，重构的复杂度不超过$O(n\log_2^2n)$，于是启发式合并暴力重构即可。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 1000005
#define M 20000005
using namespace std;
int n,m,t,A[N],B[N],F[N],si[N];
int fa[N][20],dep[N],S=19;
int TOT,LA[N],NE[N],EN[N];
int tot,rt[N],ls[M],rs[M],v[M];
bool mark[N];
void ADD(int x,int y)
{
	TOT++;
	EN[TOT]=y;
	NE[TOT]=LA[x];
	LA[x]=TOT;
}
int GF(int x)
{
	if(F[x]!=x)F[x]=GF(F[x]);
	return F[x];
}
int CO(int p)
{
	int o=++tot;
	ls[o]=ls[p];
	rs[o]=rs[p];
	v[o]=v[p];
	return o;
}
int MD(int p,int l,int r,int k)
{
	int o=CO(p);v[o]++;
	if(l==r)return o;
	int mid=l+r>>1;
	if(k<=mid)ls[o]=MD(ls[p],l,mid,k);
	else rs[o]=MD(rs[p],mid+1,r,k);
	return o;
}
void DFS(int x,int f)
{
	int i,y;
	dep[x]=dep[f]+1;
	fa[x][0]=f;
	rt[x]=MD(rt[f],1,n,A[x]);
	for(i=1;i<=S;i++)fa[x][i]=fa[fa[x][i-1]][i-1];
	for(i=LA[x];i;i=NE[i])
	{
		y=EN[i];
		if(y!=f)DFS(y,x);
	}
}
int LCA(int x,int y)
{
	if(dep[x]<dep[y])swap(x,y);
	int i,t=dep[x]-dep[y];
	for(i=0;i<=S;i++)if(t>>i&1)x=fa[x][i];
	if(x==y)return x;
	for(i=S;i>=0;i--)
	if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}
int Gans(int p1,int p2,int p3,int l,int r,int k,int x)
{
	if(l==r)return l;
	int mid=l+r>>1;
	int sum=v[ls[p1]]+v[ls[p2]]-2*v[ls[p3]]+(x>=l&&x<=mid);
	if(k<=sum)return Gans(ls[p1],ls[p2],ls[p3],l,mid,k,x);
	return Gans(rs[p1],rs[p2],rs[p3],mid+1,r,k-sum,x);
}
int main_main()
{
	int i,j,k,x,y,z,fx,fy,ans=0;char s[2];
	scanf("%d",&k);
	scanf("%d%d%d",&n,&m,&t);
	for(i=1;i<=n;i++)scanf("%d",&A[i]),B[i]=A[i];
	sort(B+1,B+n+1);
	for(i=1;i<=n;i++)A[i]=lower_bound(B+1,B+n+1,A[i])-B;
	for(i=1;i<=n;i++)F[i]=i,si[i]=1;
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		ADD(x,y);ADD(y,x);
		x=GF(x);y=GF(y);
		F[x]=y;si[y]+=si[x];
	}
	for(i=1;i<=n;i++)
	{
		x=GF(i);
		if(!mark[x])DFS(x,0);
		mark[x]=1;
	}
	while(t--)
	{
		scanf("%s",s);
		if(s[0]=='Q')
		{
			scanf("%d%d%d",&x,&y,&k);
			x^=ans;y^=ans;k^=ans;
			z=LCA(x,y);
			ans=B[Gans(rt[x],rt[y],rt[z],1,n,k,A[z])];
			printf("%d\n",ans);
		}
		else
		{
			scanf("%d%d",&x,&y);
			x^=ans;y^=ans;
			fx=GF(x);fy=GF(y);
			if(si[fx]>si[fy])swap(x,y);
			F[fx]=fy;si[fy]+=si[fx];
			ADD(x,y);ADD(y,x);
			fa[x][0]=y;DFS(x,y);
		}
	}
}
const int main_stack=16;
char my_stack[128<<21];
int main() {
  __asm__("movl %%esp, (%%eax);\n"::"a"(my_stack):"memory");
  __asm__("movl %%eax, %%esp;\n"::"a"(my_stack+sizeof(my_stack)-main_stack):"%esp");
  main_main();
  __asm__("movl (%%eax), %%esp;\n"::"a"(my_stack):"%esp");
  return 0;
}