首页 > 代码库 > 【bzoj2333】[SCOI2011]棘手的操作 可并堆+STL-set

【bzoj2333】[SCOI2011]棘手的操作 可并堆+STL-set

题目描述

N个节点,标号从1N,这N个节点一开始相互不连通。第i个节点的初始权值为a[i],接下来有如下一些操作:

U x y: 加一条边,连接第x个节点和第y个节点

A1 x v: 将第x个节点的权值增加v

A2 x v: 将第x个节点所在的连通块的所有节点的权值都增加v

A3 v: 将所有节点的权值都增加v

F1 x: 输出第x个节点当前的权值

F2 x: 输出第x个节点所在的连通块中,权值最大的节点的权值

F3: 输出所有节点中,权值最大的节点的权值

输入

输入的第一行是一个整数N,代表节点个数。

接下来一行输入N个整数,a[1], a[2], …, a[N],代表N个节点的初始权值。

再下一行输入一个整数Q,代表接下来的操作数。

最后输入Q行,每行的格式如题目描述所示。

输出

对于操作F1, F2, F3,输出对应的结果,每个结果占一行。

样例输入

3
0 0 0
8
A1 3 -20
A1 2 20
U 1 3
A2 1 10
F1 3
F2 3
A3 -10
F3

样例输出

-10
10
10


题解

可并堆+STL-set

题目中要求维护一个数据结构,支持连通块合并、单点修改、连通块修改、单点查询、连通块查询,可并堆无疑是最好的选择。

对于F3操作,再用一个set维护一下每个连通块的最大值即可。A3操作的话直接记录一下总体加了多少,询问时再加入答案。

这样嘴上说起来还是挺容易的,然而事实上细节超多。

1.使用set时要时刻注意是否该加东西,是否该删东西,以及不要“不小心”删到不存在的元素(不然无故RE死得不知有多惨)

2.可并堆树高是logn的!这意味着并不需要使用并查集即可完成所有操作,查询连通块时直接不断向上寻找fa即可。

代码看起来还是挺简单的

另外亲测左偏树和斜堆差不多,代码中写了左偏树

#include <cstdio>#include <set>#define N 300010using namespace std;multiset<int> s;multiset<int>::iterator it;int w[N] , fa[N] , l[N] , r[N] , d[N] , add[N];char str[5];void pushdown(int x){	if(add[x]) w[l[x]] += add[x] , w[r[x]] += add[x] , add[l[x]] += add[x] , add[r[x]] += add[x] , add[x] = 0;}void update(int x){	if(fa[x]) update(fa[x]);	pushdown(x);}int find(int x){	return fa[x] ? find(fa[x]) : x;}int merge(int x , int y){	if(!x) return y;	if(!y) return x;	pushdown(x) , pushdown(y);	if(w[x] < w[y]) swap(x , y);	r[x] = merge(r[x] , y) , fa[r[x]] = x;	if(d[l[x]] < d[r[x]]) swap(l[x] , r[x]);	d[x] = d[r[x]] + 1;	return x;}int clear(int x){	int t = merge(l[x] , r[x]) , f = fa[x];	fa[x] = l[x] = r[x] = 0;	if(x == l[f]) l[f] = t;	else r[f] = t;	fa[t] = f;	return find(t);}void del(int x){	s.erase(s.find(x));}int main(){	int n , i , m , v = 0 , x , y , tx , ty;	scanf("%d" , &n);	for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &w[i]) , s.insert(w[i]);	scanf("%d" , &m);	d[0] = -1;	while(m -- )	{		scanf("%s" , str);		if(str[0] == ‘U‘)		{			scanf("%d%d" , &x , &y) , tx = find(x) , ty = find(y);			if(tx != ty)			{				if(merge(tx , ty) == tx) del(w[ty]);				else del(w[tx]);			}		}		else if(str[0] == ‘A‘)		{			scanf("%d" , &x);			if(str[1] == ‘1‘) scanf("%d" , &y) , update(x) , del(w[find(x)]) , w[x] += y , s.insert(w[merge(x , clear(x))]);			else if(str[1] == ‘2‘) scanf("%d" , &y) , tx = find(x) , del(w[tx]) , w[tx] += y , s.insert(w[tx]) , add[tx] += y;			else v += x;		}		else		{			if(str[1] == ‘1‘) scanf("%d" , &x) , update(x) , printf("%d\n" , w[x] + v);			else if(str[1] == ‘2‘) scanf("%d" , &x) , tx = find(x) , printf("%d\n" , w[tx] + v);			else printf("%d\n" , *(--s.end()) + v);		}	}	return 0;}

 

 

【bzoj2333】[SCOI2011]棘手的操作 可并堆+STL-set