BZOJ2733 永无乡【splay启发式合并】

2733: [HNOI2012]永无乡

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 4190 Solved: 2226
[Submit][Status][Discuss]

Description

永无乡包含 n 座岛，编号从 1 到 n，每座岛都有自己的独一无二的重要度，按照重要度可以将这 n 座岛排名，名次用 1 到 n 来表示。某些岛之间由巨大的桥连接，通过桥可以从一个岛到达另一个岛。如果从岛 a 出发经过若干座（含 0 座）桥可以到达岛 b，则称岛 a 和岛 b 是连通的。现在有两种操作：B x y 表示在岛 x 与岛 y 之间修建一座新桥。Q x k 表示询问当前与岛 x连通的所有岛中第 k 重要的是哪座岛，即所有与岛 x 连通的岛中重要度排名第 k 小的岛是哪座，请你输出那个岛的编号。

Input

输入文件第一行是用空格隔开的两个正整数 n 和 m，分别表示岛的个数以及一开始存在的桥数。接下来的一行是用空格隔开的 n 个数，依次描述从岛 1 到岛 n 的重要度排名。随后的 m 行每行是用空格隔开的两个正整数 ai 和 bi，表示一开始就存在一座连接岛 ai 和岛 bi 的桥。后面剩下的部分描述操作，该部分的第一行是一个正整数 q，表示一共有 q 个操作，接下来的 q 行依次描述每个操作，操作的格式如上所述，以大写字母 Q 或B 开始，后面跟两个不超过 n 的正整数，字母与数字以及两个数字之间用空格隔开。对于 20%的数据 n≤1000,q≤1000

对于 100%的数据 n≤100000,m≤n，q≤300000

Output

对于每个 Q x k 操作都要依次输出一行，其中包含一个整数，表示所询问岛屿的编号。如果该岛屿不存在，则输出-1。

Sample Input

5 1
4 3 2 5 1
1 2
7
Q 3 2
Q 2 1
B 2 3
B 1 5
Q 2 1
Q 2 4
Q 2 3

Sample Output

-1
2
5
1
2

题解

这道题需要我们合并各个联通块并询问第k大

询问第k大可以用splay实现，但如何合并呢？

将两棵中较小的那一棵的节点全部取出来插入另一颗

这么暴力不会超时么？

我们最多合并n - 1次，每次尽量将相同大小的联通块合并，总共最多插入(n / 2) * logn次

所以总的复杂度O(nlog^2n)

【打个splay都打错调了半天= =】

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define isr(u) (e[e[u].f].ch[1] == u)
#define sizl(u) (e[e[u].ch[0]].siz)
using namespace std;
const int maxn = 100005,maxm = 100005,INF = 1000000000;
inline int read(){
	int out = 0,flag = 1;char c = getchar();
	while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}
	while (c >= 48 && c <= 57) {out = out * 10 + c - 48; c = getchar();}
	return out * flag;
}
int rt = 0,pre[maxn],n,m,q;
struct node{int v,f,ch[2],siz;}e[maxn];
int find(int u) {return u == pre[u] ? u : pre[u] = find(pre[u]);}
inline void pu_p(int u){e[u].siz = e[e[u].ch[0]].siz + 1 + e[e[u].ch[1]].siz;}
inline void spin(int u){
	int s = isr(u),fa = e[u].f;
	e[u].f = e[fa].f;
	if (e[fa].f) e[e[fa].f].ch[isr(fa)] = u;
	e[fa].ch[s] = e[u].ch[s ^ 1];
	if (e[u].ch[s ^ 1]) e[e[u].ch[s ^ 1]].f = fa;
	e[fa].f = u;
	e[u].ch[s ^ 1] = fa;
	pu_p(fa); pu_p(u);
}
inline void splay(int u){
	while (e[u].f){
		if (!e[e[u].f].f) spin(u);
		else if (isr(u) ^ isr(e[u].f)) spin(u),spin(u);
		else spin(e[u].f),spin(u);
	}
	rt = u;
}
inline void insert(int p){
	int u = rt,f = 0,v = e[p].v;
	while(u) f = u,u = v < e[u].v ? e[u].ch[0] : e[u].ch[1];
	e[f].ch[v > e[f].v] = p; e[p].f = f;
	splay(p);
}
inline int Kth(int u,int k){
	splay(u); int Lsiz = 0;
	while (u){
		int t = Lsiz + sizl(u);
		if (k <= t) u = e[u].ch[0];
		else if (k == t + 1) return u;
		else Lsiz = t + 1,u = e[u].ch[1];
	}
	return -1;
}
inline void order(int u){
	int l = e[u].ch[0],r = e[u].ch[1];
	e[u].siz = 1; e[u].ch[0] = e[u].ch[1]  = e[u].f = 0;
	if (l) order(l);
	insert(u);
	if (r) order(r);
}
inline void Merge(int u,int v){
	if (u == v) return;
	pre[v] = u;
	splay(v); splay(u);
	if (e[u].siz < e[v].siz) swap(u,v);
	rt = u;
	order(v);
}
int main()
{
	int fa,fb,x,k;
	char c;
	n = read(); m = read();
	REP(i,n) e[i].v = read(),e[i].siz = 1,pre[i] = i,e[i].ch[0] = e[i].ch[1] = e[i].f = 0;
	REP(i,m) fa = find(read()),fb = find(read()),Merge(fa,fb);
	q = read();
	REP(i,q){
		c = getchar();
		while (c != 'B' && c != 'Q') c = getchar();
		if (c == 'B'){
			fa = find(read()); fb = find(read());
			Merge(fa,fb);
		}
		else { x = find(read()); k = read(); printf("%d
",Kth(x,k));}
	}
	return 0;
}

BZOJ2733 永无乡 【splay启发式合并】