传送门
启发式合并菜题。
题意：支持与连通块有关的几种操作。
要求支持连边，单点修改，连通块修改，全局修改和单点查值，连通块查最大值和全局最大值。
我们对每个连通块和答案用可删堆维护最大值，然后用启发式合并来解决连边的问题。
关键在于连通块修改，这个可以给每个连通块维护一个标记，然后在合并的时候每个数记得修改值就行了。
代码
#include<bits/stdc++.h>
#define ri register int
using namespace std;
inline int read(){int ans=0,w=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();return ans*w;
}
const int N=3e5+5;
struct IN_OUT_priority_queue{priority_queue<int>a,b;inline void push(const int&x){a.push(x);}inline void del(const int&x){b.push(x);}inline int top(){while(b.size()&&a.top()==b.top())a.pop(),b.pop();return a.top();}inline int size(){return a.size()-b.size();}
}ans,S[N];
int n,fa[N],det[N],val[N],all=0;
vector<int>id[N];
inline int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
inline void solve1(){int x=find(read()),y=find(read());if(x==y)return;if(id[x].size()<id[y].size())swap(x,y);fa[y]=x,ans.del(S[x].top()+det[x]),ans.del(S[y].top()+det[y]);for(ri i=0;i<id[y].size();++i)id[x].push_back(id[y][i]),val[id[y][i]]+=det[y]-det[x],S[x].push(val[id[y][i]]);ans.push(S[x].top()+det[x]);
}
inline void solve2(){int x=read(),fx=find(x),y=read();ans.del(S[fx].top()+det[fx]);S[fx].del(val[x]),S[fx].push(val[x]+=y);ans.push(S[fx].top()+det[fx]);
}
inline void solve3(){int x=find(read()),v=read();ans.del(S[x].top()+det[x]),det[x]+=v,ans.push(S[x].top()+det[x]);}
inline void solve4(){all+=read();}
inline void solve5(){int x=read();cout<<val[x]+det[find(x)]+all<<'\n';}
inline void solve6(){int x=find(read());cout<<S[x].top()+det[x]+all<<'\n';}
inline void solve7(){cout<<ans.top()+all<<'\n';}
int main(){n=read();for(ri i=1;i<=n;++i)id[i].push_back(i),fa[i]=i,S[i].push(val[i]=read()),ans.push(val[i]);for(ri tt=read(),a,b,op;tt;--tt){string s;cin>>s;if(s=="U")solve1();if(s=="A1")solve2();if(s=="A2")solve3();if(s=="A3")solve4();if(s=="F1")solve5();if(s=="F2")solve6();if(s=="F3")solve7();}return 0;
}