sol
左偏树。
这题目真的是调死我了。
左偏树删除任意节点：把这个点的左右子树合并接在原来的父亲上，再一路往上更新一下(dis)即可。注意特判删除的点原先就是根的情况。
对于全局最大值，写一个可删除的双堆结构（也可以写multiset），维护每个联通块的堆顶（保证每个联通块只贡献一个），所以在修改的时候要注意删除和加入。
七个操作：
U：左偏树合并，删除一个堆中元素，注意判原本已连通的情况
A1：删除那个点，然后修改后插入
A2：暴力跳到根然后直接打标记
A3：开全局变量记录
F1：下放所有标记
F2：暴跳到根输出
F3：输出堆顶元素
code
我真的是调了两个小时
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 300005;
int gi()
{
int x=0,w=1;char ch=getchar();
while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if (ch=='-') w=0,ch=getchar();
while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return w?x:-x;
}
int n,m,fa[N],ls[N],rs[N],key[N],dis[N],tag[N],Stack[N],top,sum;
char s[10];
struct Heap{
priority_queue<int>a,d;
void push(int x){a.push(x);}
void del(int x){d.push(x);}
void clear(){while (!d.empty()&&a.top()==d.top()) a.pop(),d.pop();}
int top(){clear();return a.top();}
}Q;
void cover(int x,int val){key[x]+=val;tag[x]+=val;}
void pushdown(int x)
{
if (ls[x]) cover(ls[x],tag[x]);
if (rs[x]) cover(rs[x],tag[x]);
tag[x]=0;
}
void alldown(int x)
{
Stack[top=1]=x;
for (int i=x;fa[i];i=fa[i])
Stack[++top]=fa[i];
while (top) pushdown(Stack[top--]);
}
int getroot(int x)
{
while (fa[x]) x=fa[x];
return x;
}
int Merge(int x,int y)
{
if (!x||!y) return x|y;
if (key[x]<key[y]) swap(x,y);
pushdown(x);pushdown(y);
rs[x]=Merge(rs[x],y);
fa[rs[x]]=x;
if (dis[ls[x]]<dis[rs[x]]) swap(ls[x],rs[x]);
dis[x]=dis[rs[x]]+1;
return x;
}
void update(int x)
{
while (x)
{
if (dis[ls[x]]<dis[rs[x]]) swap(ls[x],rs[x]);
dis[x]=dis[rs[x]]+1;
x=fa[x];
}
}
void Delete(int x)
{
alldown(x);
fa[ls[x]]=fa[rs[x]]=0;
if (x==ls[fa[x]]) ls[fa[x]]=0;
else rs[fa[x]]=0;
int y=getroot(x);
Merge(y,Merge(ls[x],rs[x]));
update(fa[x]);
fa[x]=ls[x]=rs[x]=0;
}
int main()
{
n=gi();
for (int i=1;i<=n;i++)
key[i]=gi(),Q.push(key[i]);
m=gi();
while (m--)
{
scanf("%s",s);
if (s[0]=='U')
{
int x=gi(),y=gi();
x=getroot(x);y=getroot(y);
if (x==y) continue;
int z=Merge(x,y);
Q.del(z==x?key[y]:key[x]);
}
if (s[0]=='A'&&s[1]=='1')
{
int x=gi(),v=gi();
int y=getroot(x);
if (!fa[x])
{
Q.del(key[x]);
pushdown(x);
fa[ls[x]]=fa[rs[x]]=0;
y=Merge(ls[x],rs[x]);
fa[x]=ls[x]=rs[x]=0;
}
else Delete(x),Q.del(key[y]);
key[x]+=v;
Q.push(key[Merge(x,y)]);
}
if (s[0]=='A'&&s[1]=='2')
{
int x=gi(),v=gi();
x=getroot(x);
Q.del(key[x]);
cover(x,v);
Q.push(key[x]);
}
if (s[0]=='A'&&s[1]=='3') sum+=gi();
if (s[0]=='F'&&s[1]=='1')
{
int x=gi();
alldown(x);
printf("%d
",key[x]+sum);
}
if (s[0]=='F'&&s[1]=='2')
{
int x=gi();
x=getroot(x);
printf("%d
",key[x]+sum);
}
if (s[0]=='F'&&s[1]=='3') printf("%d
",Q.top()+sum);
}
return 0;
}