真的是个很棘手的操作。。
注意每删除一个点，就需要clear一次。
#include<complex> #include<cstdio> using namespace std; const int N=3e5+7; int n,m,rot,add; //add记录所有节点增加的权值 int q[N<<1]; inline int qread() { int x=0,j=1; char ch=getchar(); while(ch<'0' || ch>'9'){if(ch=='-')j=-1;ch=getchar();} while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*j; } struct Leftist { int fat[N],son[N][2],key[N],dis[N],mark[N]; void clear(int x) { fat[x]=son[x][1]=son[x][0]=0; } void PushDown(int x) { if(!mark[x])return; if(son[x][0]) { key[son[x][0]]+=mark[x]; mark[son[x][0]]+=mark[x]; } if(son[x][1]) { key[son[x][1]]+=mark[x]; mark[son[x][1]]+=mark[x]; } mark[x]=0; } int Merge(int a,int b) { if(!a || !b)return a+b; if(key[a]<key[b])swap(a,b); PushDown(a); son[a][1]=Merge(son[a][1],b); fat[son[a][1]]=a; if(dis[son[a][1]]>dis[son[a][0]])swap(son[a][1],son[a][0]); dis[a]=dis[son[a][1]]+1; return a; } int Sum(int x) { int res=0; while(x=fat[x])res+=mark[x]; return res; } int Top(int x) { while(fat[x])x=fat[x]; return x; } int Pop(int x) { PushDown(x); int q=fat[x],p=Merge(son[x][0],son[x][1]); if(q)son[q][son[q][1]==x]=p; fat[p]=q; while(q) { if(dis[son[q][1]]>dis[son[q][0]]) swap(son[q][1],son[q][0]); if(dis[q]==dis[son[q][1]]+1)return rot; dis[q]=dis[son[q][1]]+1; p=q;q=fat[q]; } return p; } int AddPoint(int x,int v) { int t=Top(x); if(t==x) if(!son[x][1] && !son[x][0]) { key[x]+=v; return x; } else if(son[x][0])t=son[x][0]; else t=son[x][1]; Pop(x); key[x]+=v+Sum(x); clear(x); return Merge(Top(t),x); } int Build() { int head=1,tail=0; for(int i=1;i<=n;i++) q[++tail]=i; int x,y; while(tail-head) { x=q[head++];y=q[head++]; q[++tail]=Merge(x,y); } return q[head]; } }t1,t2; //对于F3操作,需要把所有堆的根拿出来建一个新的堆 //新开一棵t2来维护这些点 int main() { scanf("%d",&n); for(int i=1;i<=n;i++) t1.key[i]=t2.key[i]=qread(); rot=t2.Build(); char c[5];int x,y,r1,r2; scanf("%d",&m); while(m--) { scanf("%s",c); if(c[0]=='U') { x=qread();y=qread(); r1=t1.Top(x);r2=t1.Top(y); if(r1!=r2) { int tmp=t1.Merge(r1,r2); if(tmp==r1)t2.Pop(r2); else t2.Pop(r1); /* 合并时,若树a并到了b上,则将a从第二棵树中删除,反之则删除b 被删去的点还是可能会成为最大值的,可它已经被删除了.... 它再次成为最大值只有可能是在A1操作,将它再插入就好了 */ } } else if(c[0]=='A' && c[1]=='1') { x=qread();y=qread(); rot=t2.Pop(t1.Top(x)); int tmp=t1.AddPoint(x,y); t2.key[tmp]=t1.key[tmp]; t2.clear(tmp); rot=t2.Merge(rot,tmp); } else if(c[0]=='A' && c[1]=='2') { x=qread();y=qread(); r1=t1.Top(x); rot=t2.Pop(r1); //整个联通块都+y,不影响堆的性质,但mark不能及时下传,所以仍要把根删去后再插入 t1.key[r1]+=y;t1.mark[r1]+=y; t2.key[r1]=t1.key[r1]; t2.clear(r1); rot=t2.Merge(r1,rot); } else if(c[0]=='A' && c[1]=='3')add+=qread(); else if(c[0]=='F' && c[1]=='1') { x=qread(); printf("%d ",t1.key[x]+add+t1.Sum(x)); } else if(c[0]=='F' && c[1]=='2') { x=qread(); printf("%d ",t1.key[t1.Top(x)]+add); } else printf("%d ",t2.key[rot]+add); } return 0; }