//以后为了凑字数还是把题面搬上来吧2333
发布时间果然各种应景。。。
Time Limit: 10 Sec Memory Limit: 128 MB
Description
有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: 输出所有节点中，权值最大的节点的权值
Input
输入的第一行是一个整数N，代表节点个数。
接下来一行输入N个整数，a[1], a[2], …, a[N]，代表N个节点的初始权值。
再下一行输入一个整数Q，代表接下来的操作数。
最后输入Q行，每行的格式如题目描述所示。
Output
对于操作F1, F2, F3，输出对应的结果，每个结果占一行。
Sample Input
3
0 0 0
8
A1 3 -20
A1 2 20
U 1 3
A2 1 10
F1 3
F2 3
A3 -10
F3
0 0 0
8
A1 3 -20
A1 2 20
U 1 3
A2 1 10
F1 3
F2 3
A3 -10
F3
Sample Output
-10
10
10
10
10
HINT
对于30%的数据，保证 N<=100，Q<=10000
对于80%的数据，保证 N<=100000，Q<=100000
对于100%的数据，保证 N<=300000，Q<=300000
对于所有的数据，保证输入合法，并且 -1000<=v, a[1], a[2], …, a[N]<=1000
看到题号就2333了。。。然而被坑了一下午T_T。。。
因为操作里有合并和查询最大值，所以显然可并堆？
要用两个可并堆，一个维护各个联通块的最大值，另一个就是节点的修改查询blabla（维护联通块的那个可以善用stl。。。跪烂）。。。。
这题还有对整个联通块的增加的操作，所以我们可以打lazy标记。。
U操作的时候，如果两个节点不在同一联通块的话，把它们合并到一起，注意到合并后少了一个联通块（堆顶值较小的那个），要在维护联通块的可并堆里面删除；同时在合并的时候要下传标记。
A1操作，把x节点的值增加以后可能会破坏最大堆的性质，一种方法是修改堆节点的姿势，不断判断是否要和父亲交换；另一种是利用可并堆性质，先删除原来的x节点，增加以后再插进去。。。（显然第二种好写得多吧）。。当然了不管是哪一种姿势都要记得先把x节点还有祖先的标记下传。
然而一个令人悲伤的消息是第一种写法还要考虑负数的情况T_T，增加的值为负数的时候就是看和那个儿子交换了。。。
A2操作，在x节点所在联通块的堆顶元素打一个懒标记；
A3操作开一个全局变量存就好了= =
F1操作，因为x节点的祖先可能有标记，所以要先把x节点的所有祖先从上到下依次下传标记，这样才能得到x节点真实的值；
F2操作，直接输出所在联通块的堆顶元素就好了；
F3操作，输出维护各个联通块的可并堆顶的值。
蒟蒻一开始用左偏树的时候删除节点还要维护距离各种蛋疼。。还写挂调了半天，换成斜堆立马过。。。
斜堆代码：
#include<cstdio>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int maxn=;
struct zs1{
int c[],/*dis,*/val,fa;
int add;
}tree[maxn];
struct zs2{
int c[],val,fa;
//dis,
}tree1[maxn];
int i,j,k,n,m,alladd,x,y,q,root1,tmpp;
int stack[maxn];
char id[]; int getroot(int x){
while(tree[x].fa)x=tree[x].fa;return x;
}
void pushdown(int x){
if(tree[x].add==)return;
int l=tree[x].c[],r=tree[x].c[],add=tree[x].add;
if(l)tree[l].add+=add,tree[l].val+=add;
if(r)tree[r].add+=add,tree[r].val+=add;
tree[x].add=;
}
void pushalldown(int x){
int top=;
while(x)stack[++top]=x,x=tree[x].fa;
for(;top;top--)pushdown(stack[top]);
}
int merge1(int a,int b){
if(a==||b==)return a+b;
if(tree1[a].val<tree1[b].val)swap(a,b);
tree1[a].c[]=merge1(tree1[a].c[],b);
int l=tree1[a].c[],r=tree1[a].c[];
tree1[r].fa=a;
swap(tree1[a].c[],tree1[a].c[]);
return a;
}
void del1(int x){
int fa=tree1[x].fa,newson=merge1(tree1[x].c[],tree1[x].c[]);
tree1[x].fa=tree1[x].c[]=tree1[x].c[]=;
if(newson)tree1[newson].fa=fa;
tree1[fa].c[tree1[fa].c[]==x]=newson;
if(!fa)root1=newson;
}
int merge(int a,int b){
if(a==||b==)return a+b;
if(tree[a].val<tree[b].val)swap(a,b);
pushdown(a);
tree[a].c[]=merge(tree[a].c[],b);
int l=tree[a].c[],r=tree[a].c[];
tree[r].fa=a;
swap(tree[a].c[],tree[a].c[]);
return a;
}
void del(int x){
pushalldown(x);
int newson=merge(tree[x].c[],tree[x].c[]),fa=tree[x].fa;
tree[x].c[]=tree[x].c[]=tree[x].fa=;
if(newson)tree[newson].fa=fa;
tree[fa].c[tree[fa].c[]==x]=newson;
if(fa)tmpp=getroot(fa);else tmpp=getroot(newson);
}
void runA1(int x,int v){
pushalldown(x);
int preroot=getroot(x);
int fa=tree[x].fa;
del(x);
tree[x].val+=v;
merge(tmpp,x);
int nowroot=getroot(x);
if(nowroot!=preroot||fa==){
del1(preroot);
tree1[nowroot].val=tree[nowroot].val;
root1=merge1(root1,nowroot);
}
}
void runA2(int x,int y){
x=getroot(x);
tree[x].add+=y;tree[x].val+=y;
del1(x);
tree1[x].val=tree[x].val;
root1=merge1(root1,x);
}
void runU(int x,int y){
int t[];
t[]=getroot(x);t[]=getroot(y);
if(t[]!=t[])
del1(t[t[]==merge(t[],t[])]);
}
int main(){
tree[].val=-;
scanf("%d",&n);
for(i=;i<=n;i++)scanf("%d",&tree[i].val),tree1[i].val=tree[i].val;
for(i=;i<=n;i++)root1=merge1(root1,i);
scanf("%d",&q);
while(q--){
scanf("%s",id);
if(id[]=='U'){
scanf("%d%d",&x,&y);
runU(x,y);
}else
if(id[]=='A'){
scanf("%d",&x);if(id[]!='')scanf("%d",&y);
if(id[]=='')runA1(x,y);
if(id[]=='')runA2(x,y);
if(id[]=='')alladd+=x;
}else
if(id[]=='F'){
if(id[]!='')scanf("%d",&x);
if(id[]==''){
pushalldown(x);
printf("%d\n",tree[x].val+alladd);
}
if(id[]=='')printf("%d\n",tree[getroot(x)].val+alladd);
if(id[]=='')printf("%d\n",tree1[root1].val+alladd);
}
}
return ;
}
左偏树（其实只有几行不一样= =）：
#include<cstdio>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int maxn=;
struct zs1{
int c[],dis,val,fa;
int add;
}tree[maxn];
struct zs2{
int c[],dis,val,fa;
}tree1[maxn];
int i,j,k,n,m,alladd,x,y,q,root1,tmpp;
int stack[maxn];
char id[]; int getroot(int x){
while(tree[x].fa)x=tree[x].fa;return x;
}
void pushdown(int x){
if(tree[x].add==)return;
int l=tree[x].c[],r=tree[x].c[],add=tree[x].add;
if(l)tree[l].add+=add,tree[l].val+=add;
if(r)tree[r].add+=add,tree[r].val+=add;
tree[x].add=;
}
void pushalldown(int x){
int top=;
while(x)stack[++top]=x,x=tree[x].fa;
for(;top;top--)pushdown(stack[top]);
}
int merge1(int a,int b){
if(a==||b==)return a+b;
if(tree1[a].val<tree1[b].val)swap(a,b);
tree1[a].c[]=merge1(tree1[a].c[],b);
int l=tree1[a].c[],r=tree1[a].c[];
tree1[r].fa=a;
if(tree1[l].dis<tree1[r].dis)swap(tree1[a].c[],tree1[a].c[]);
tree1[a].dis=tree1[r].dis+;
return a;
}
void del1(int x){
int fa=tree1[x].fa,newson=merge1(tree1[x].c[],tree1[x].c[]);
tree1[x].fa=tree1[x].c[]=tree1[x].c[]=;
if(newson)tree1[newson].fa=fa;
if(fa){
tree1[fa].c[tree1[fa].c[]==x]=newson;
while(fa){
int pre=tree1[fa].dis;
if(tree1[tree1[fa].c[]].dis>tree1[tree1[fa].c[]].dis)swap(tree1[fa].c[],tree1[fa].c[]);
tree1[fa].dis=tree1[tree1[fa].c[]].dis+;
if(tree1[fa].dis==pre)break;
fa=tree1[fa].fa;
}
}
else root1=newson;
}
int merge(int a,int b){
if(a==||b==)return a+b;
if(tree[a].val<tree[b].val)swap(a,b);
pushdown(a);
tree[a].c[]=merge(tree[a].c[],b);
int l=tree[a].c[],r=tree[a].c[];
tree[r].fa=a;
if(tree[l].dis<tree[r].dis)swap(tree[a].c[],tree[a].c[]);
tree[a].dis=tree[tree[a].c[]].dis+;
return a;
}
void del(int x){
pushalldown(x);
int newson=merge(tree[x].c[],tree[x].c[]),fa=tree[x].fa;
tree[x].c[]=tree[x].c[]=tree[x].fa=;
if(newson)tree[newson].fa=fa;
if(!fa)tmpp=getroot(newson);else tmpp=getroot(fa);
if(fa){
tree[fa].c[tree[fa].c[]==x]=newson;
while(fa&&tree[fa].c[]){
int pre=tree[fa].dis;
if(tree[tree[fa].c[]].dis>tree[tree[fa].c[]].dis)swap(tree[fa].c[],tree[fa].c[]);
tree[fa].dis=tree[tree[fa].c[]].dis+;
if(tree[fa].dis==pre)break;
fa=tree[fa].fa;
}
}
//if(newson)tmpp=getroot(newson);
//else tmpp=getroot(fa);//这里是错的，如果维护距离的时候fa跑到了0节点就会挂TAT
}
void runA1(int x,int v){
pushalldown(x);
int preroot=getroot(x);
int fa=tree[x].fa;
del(x);
tree[x].val+=v;
merge(tmpp,x);
int nowroot=getroot(x);
if(nowroot!=preroot||fa==){
del1(preroot);
tree1[nowroot].val=tree[nowroot].val;
root1=merge1(root1,nowroot);
}
}
void runU(int x,int y){
int t[];
t[]=getroot(x);t[]=getroot(y);
if(t[]!=t[])
del1(t[t[]==merge(t[],t[])]);
}
void runA2(int x,int y){
x=getroot(x);
tree[x].add+=y;tree[x].val+=y;
del1(x);
tree1[x].val=tree[x].val;
root1=merge1(root1,x);
}
int main(){
tree[].dis=tree1[].dis=-;
tree[].val=-;
scanf("%d",&n);
for(i=;i<=n;i++)scanf("%d",&tree[i].val),tree1[i].val=tree[i].val;
for(i=;i<=n;i++)root1=merge1(root1,i);
scanf("%d",&q);
while(q--){
scanf("%s",id);
if(id[]=='U'){
scanf("%d%d",&x,&y);
runU(x,y);
}else
if(id[]=='A'){
scanf("%d",&x);if(id[]!='')scanf("%d",&y);
if(id[]=='')runA1(x,y);
if(id[]=='')runA2(x,y);
if(id[]=='')alladd+=x;
}else
if(id[]=='F'){
if(id[]!='')scanf("%d",&x);
if(id[]==''){
pushalldown(x);
printf("%d\n",tree[x].val+alladd);
}
if(id[]=='')printf("%d\n",tree[getroot(x)].val+alladd);
if(id[]=='')printf("%d\n",tree1[root1].val+alladd);
}
}
return ;
}
最近几道可并堆用斜堆和左偏树似乎毫无差异。。。斜堆大法好！