欢迎访问~原文出处——博客园-zhouzhendong
去博客园看该题解
题目传送门 - BZOJ2333
题意概括
有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: 输出所有节点中，权值最大的节点的权值
题解
我比较懒。
这是一道坑坑的细节题。
我调了大约6个小时。
对于A3，我们只需要保存一个全局变量，每次输出的时候加上去就可以了。
对于F3，我们只需要弄一个multiset就可以了。
对于U、A1、A2、F1、F2，就是左偏树的几个基本操作。
“嘴巴上AC就是简单”
代码
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <set>
#include <vector>
using namespace std;
const int N=300005,Inf=1e8;
int n,m,addv=0;
struct Tree{
int fa,ls,rs,v,add,len;
Tree (){}
Tree (int a,int b,int c,int d,int e,int f){
fa=a,ls=b,rs=c,v=d,add=e,len=f;
}
}t[N];
multiset <int> rts;
void check0(){
t[0]=Tree(0,0,0,-Inf,0,-1);
}
int getroot(int x){
check0();
while (t[x].fa)
x=t[x].fa;
return x;
}
void del(int x){
rts.erase(rts.find(x));
}
void pushdown(int x){
check0();
int s,&add=t[x].add;
if (!t[x].add)
return;
s=t[x].ls;
if (s)
t[s].add+=add,t[s].v+=add;
s=t[x].rs;
if (s)
t[s].add+=add,t[s].v+=add;
add=0;
}
void pushadd(int x){
check0();
if (t[x].fa)
pushadd(t[x].fa);
pushdown(x);
}
int merge(int a,int b){
check0();
if (a==b)
return a;
if (a==0)
return b;
if (b==0)
return a;
if (t[a].v<t[b].v)
swap(a,b);
pushdown(a);
t[a].rs=merge(t[a].rs,b);
t[t[a].rs].fa=a;
if (t[t[a].ls].len<t[t[a].rs].len)
swap(t[a].ls,t[a].rs);
t[a].len=t[t[a].rs].len+1;
return a;
}
void change(int x,int val){
check0();
pushadd(x);
int rt=getroot(x),maxv=t[rt].v;
int fa=t[x].fa,s=merge(t[x].ls,t[x].rs);
if (fa==0&&s==0){
del(t[x].v);
t[x].v=val;
rts.insert(t[x].v);
return;
}
t[s].fa=0;
if (fa){
t[s].fa=fa;
if (t[fa].ls==x)
t[fa].ls=s;
else
t[fa].rs=s;
}
t[x]=Tree(0,0,0,val,0,0);
merge(x,getroot(s?s:fa));
int maxv_=t[getroot(x)].v;
if (maxv_!=maxv){
del(maxv);
rts.insert(maxv_);
}
}
int main(){
scanf("%d",&n);
check0();
rts.clear();
for (int i=1,v;i<=n;i++){
scanf("%d",&v);
t[i]=Tree(0,0,0,v,0,0);
rts.insert(v);
}
scanf("%d",&m);
while (m--){
char op[5],c1,c2;
int a,b;
scanf("%s",op),c1=op[0],c2=op[1];
if (c1=='U'){
scanf("%d%d",&a,&b);
a=getroot(a),b=getroot(b);
if (a==b)
continue;
if (t[a].v<t[b].v)
swap(a,b);
del(t[b].v);
merge(a,b);
}
else if (c1=='A'){
if (c2=='1')
scanf("%d%d",&a,&b),pushadd(a),change(a,t[a].v+b);
else if (c2=='2'){
scanf("%d%d",&a,&b);
a=getroot(a);
del(t[a].v);
t[a].add+=b,t[a].v+=b;
rts.insert(t[a].v);
}
else
scanf("%d",&a),addv+=a;
}
else {
if (c2=='1')
scanf("%d",&a),pushadd(a),printf("%d
",t[a].v+addv);
else if (c2=='2')
scanf("%d",&a),printf("%d
",t[getroot(a)].v+addv);
else
printf("%d
",*--rts.end()+addv);
}
}
return 0;
}