首页 > 代码库 > 【bzoj2333】[SCOI2011]棘手的操作 可并堆+STL-set
【bzoj2333】[SCOI2011]棘手的操作 可并堆+STL-set
题目描述
有N个节点，标号从1到N，这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