[文章目录]
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: 输出所有节点中，权值最大的节点的权值
N<=300000，Q<=300000
有合并操作，并且需要维护最大值以及带有整体和单点修改。可并堆。左偏树维护一个标记，然后在合并的时候需要下传。修改单点的话相当于删除节点，然后修改节点再和原堆合并。整体的最值直接用multiset搞一下。
#include <set>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 301000
inline void read(int &x)
{
char ch=getchar(); x=0; int f=1;
while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
x*=f;
}
multiset<int>s;
multiset<int>::iterator it;
int n,m,biglz;
struct heap
{
int fa,ls,rs,w,lz,nvl;
}h[N];
inline void pushdown(int x)
{
if(!h[x].lz) return ;
int ls=h[x].ls,rs=h[x].rs,lz=h[x].lz; h[x].lz=0;
if(ls) h[ls].w+=lz,h[ls].lz+=lz;
if(rs) h[rs].w+=lz,h[rs].lz+=lz;
}
int merge(int x,int y)
{
if(!x||!y) return x|y;
if(h[x].w<h[y].w) swap(x,y);
pushdown(x); h[x].rs=merge(h[x].rs,y); h[h[x].rs].fa=x;
if(h[h[x].ls].nvl<h[h[x].rs].nvl) swap(h[x].ls,h[x].rs);
h[x].nvl=h[h[x].rs].nvl+1;
return x;
}
void pushall(int x) {if(h[x].fa) pushall(h[x].fa); pushdown(x);}
void getnvl(int x)
{
if(!x) return ;
if(h[h[x].ls].nvl<h[h[x].rs].nvl) swap(h[x].ls,h[x].rs);
if(h[x].nvl==h[h[x].rs].nvl+1) return ;
h[x].nvl=h[h[x].rs].nvl+1; getnvl(h[x].fa);
}
inline int pop(int x)
{
pushall(x);
int tmp=merge(h[x].ls,h[x].rs),fa=h[x].fa;
if(tmp) h[tmp].fa=fa;
if(fa)
{
if(x==h[fa].ls) h[fa].ls=tmp;
else h[fa].rs=tmp;
getnvl(fa);
}
h[x].ls=h[x].rs=h[x].fa=0; h[x].nvl=1;
return tmp;
}
inline int find(int x){while(h[x].fa) x=h[x].fa; return x;}
int main()
{
read(n); int x,y,fa,i;
for(i=1;i<=n;++i) read(x),s.insert(x),h[i].nvl=1,h[i].w=x;
read(m); char sw[10];
while(m--)
{
scanf("%s",sw);
if(sw[0]=='U')
{
read(x); read(y); x=find(x); y=find(y);
if(x!=y)
{
if(merge(x,y)==x) s.erase(s.find(h[y].w));
else s.erase(s.find(h[x].w));
}
}
if(sw[0]=='A')
{
switch(sw[1])
{
case '1':
{
read(x); read(y); s.erase(s.find(h[find(x)].w));
if(h[x].fa) fa=find(x),pop(x);
else fa=pop(x); h[x].w+=y;
fa=merge(fa,x); s.insert(h[fa].w); break;
}
case '2':
{
read(x); read(y); x=find(x); s.erase(s.find(h[x].w));
h[x].w+=y; h[x].lz+=y; s.insert(h[x].w); break;
}
case '3':read(x); biglz+=x; break;
}
}
if(sw[0]=='F')
{
switch(sw[1])
{
case '1': read(x); pushall(x); printf("%d\n",h[x].w+biglz); break;
case '2': read(x); x=find(x); printf("%d\n",h[x].w+biglz); break;
case '3': it=s.end(); it--; printf("%d\n",(*it)+biglz); break;
}
}
}
return 0;
}