【bzoj2733】[HNOI2012]永无乡 Treap启发式合并

题目描述

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

输入

输入文件第一行是用空格隔开的两个正整数 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

输出

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

样例输入

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

样例输出

-1
2
5
1
2

题解

Treap启发式合并。

启发式合并就是直接把节点少的Treap强行拆掉并加到节点多的Treap里面，期望时间复杂度O(nlogn*logn)，注意点细节啥的。

一开始居然把f和root弄混了。。。一顿乱码之下竟然还A了。。。代码已改正。

#include <cstdio>

#include <cstdlib>

#include <algorithm>

using namespace std;

int val[100010] , l[100010] , r[100010] , si[100010] , rnd[100010] , root[100010] , f[100010];

char str[10];

int find(int x)

{

	return x == f[x] ? x : f[x] = find(f[x]);

}

void zig(int &k)

{

	int t = l[k];

	l[k] = r[t];

	r[t] = k;

	si[t] = si[k];

	si[k] = si[l[k]] + si[r[k]] + 1;

	k = t;

}

void zag(int &k)

{

	int t = r[k];

	r[k] = l[t];

	l[t] = k;

	si[t] = si[k];

	si[k] = si[l[k]] + si[r[k]] + 1;

	k = t;

}

void ins(int target , int &k , int v)

{

	if(!k)

	{

		k = target;

		val[k] = v;

		si[k] = 1;

		rnd[k] = rand();

		return;

	}

	si[k] ++ ;

	if(v < val[k])

	{

		ins(target , l[k] , v);

		if(rnd[l[k]] < rnd[k]) zig(k);

	}

	else

	{

		ins(target , r[k] , v);

		if(rnd[r[k]] < rnd[k]) zag(k);

	}

}

int query(int k , int x)

{

	if(x <= si[l[k]]) return query(l[k] , x);

	else if(x == si[l[k]] + 1) return k;

	else return query(r[k] , x - si[l[k]] - 1);

}

void cls(int k , int x)

{

	if(!k) return;

	cls(l[k] , x) , cls(r[k] , x);

	l[k] = r[k] = si[k] = rnd[k] = 0;

	ins(k , root[x] , val[k]);

}

void merge(int x , int y)

{

	int tx = find(x) , ty = find(y);

	if(tx != ty)

	{

		if(si[root[tx]] < si[root[ty]]) swap(tx , ty);

		cls(ty , tx);

		f[ty] = tx;

	}

}

int main()

{

	int n , m , q , i , x , y;

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

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

		scanf("%d" , &x) , f[i] = i , ins(i , root[i] , x);

	while(m -- )

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

	scanf("%d" , &q);

	while(q -- )

	{

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

		if(str[0] == 'Q') printf("%d\n" , si[root[find(x)]] >= y ? query(root[f[x]] , y) : -1);

		else merge(x , y);

	}

	return 0;

}

巴特西

【bzoj2733】[HNOI2012]永无乡 Treap启发式合并

最新文章

热门文章