一道恶心至极的左偏树题
题意:
题解：
- 观察操作可以发现需要用两棵左偏树来维护 一棵维护全局最大值 一棵维护正常
- 操作一：普通左偏树正常连边 全局左偏树可以删去小的那个点
- 操作二：普通左偏树正常操作（删点-增值-merge）全局左偏树先删去x点连通块祖先 然后再加回连通块祖先 这样做比对全局左偏树也正常操作有优越性 点会越来越少 如果全局左偏树也和局部左偏树一样操作会MLE
- 操作三：和操作二非常相似 普通左偏树的根部加一个值和懒标记即可 全局左偏树类似操作二
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=3e5+10; int n,m,x,y,z,a[N],outdata,root; struct zps { int lson[N],rson[N],val[N],dis[N],fa[N],col[N]; void clear(int x){lson[x]=rson[x]=fa[x]=0;} int getlazy(int x){int ans=0;while(x=fa[x])ans+=col[x];return ans;} void down(int x) { if(lson[x])val[lson[x]]+=col[x],col[lson[x]]+=col[x]; if(rson[x])val[rson[x]]+=col[x],col[rson[x]]+=col[x]; col[x]=0; } int merge(int x,int y) { if(!x||!y)return x+y; if(val[x]<val[y])swap(x,y); down(x); rson[x]=merge(rson[x],y); fa[rson[x]]=x; if(dis[rson[x]]>dis[lson[x]])swap(lson[x],rson[x]); dis[x]=dis[rson[x]]+1; return x; } int getfa(int x){while(fa[x])x=fa[x];return x;} int delet(int x) { down(x); int fx=fa[x]; int temproot=merge(lson[x],rson[x]); fa[temproot]=fx; if(fx&&lson[fx]==x)lson[fx]=temproot; else if(fx&&rson[fx]==x)rson[fx]=temproot; while(fx) { if(dis[lson[fx]]<dis[rson[fx]])swap(rson[fx],lson[fx]); dis[fx]=dis[rson[fx]]+1; temproot=fx; fx=fa[fx]; } return temproot; } int add(int x,int v) { int fx=getfa(x); if(fx==x) { if(lson[x]+rson[x]==0){val[x]+=v;return x;} else if(lson[x])fx=lson[x]; else if(rson[x])fx=rson[x]; } delet(x); val[x]+=getlazy(x)+v; clear(x); return merge(getfa(fx),x);//note } int build() { queue<int>t; for(int i=1;i<=n;i++)t.push(i); int x,y,z; while(t.size()>1) { x=t.front();t.pop(); y=t.front();t.pop(); z=merge(x,y);t.push(z); } return t.front(); } }in,out; char op[10]; int main() { in.dis[0]=out.dis[0]=-1; cin>>n; for(int i=1;i<=n;i++)scanf("%d",&a[i]),in.val[i]=out.val[i]=a[i]; root=out.build(); cin>>m; while(m--) { scanf("%s",op+1); if(op[1]=='A') { if(op[2]=='1') { scanf("%d%d",&x,&y); root=out.delet(in.getfa(x)); int temp=in.add(x,y); out.val[temp]=in.val[temp]; out.clear(temp); root=out.merge(temp,root); } if(op[2]=='2') { scanf("%d%d",&x,&y); int fx=in.getfa(x); root=out.delet(fx); in.val[fx]+=y; in.col[fx]+=y; out.val[fx]=in.val[fx]; out.clear(fx); root=out.merge(root,fx); } if(op[2]=='3')scanf("%d",&x),outdata+=x; } if(op[1]=='F') { if(op[2]=='1')scanf("%d",&x),printf("%d\n",in.val[x]+in.getlazy(x)+outdata); if(op[2]=='2')scanf("%d",&x),printf("%d\n",in.val[in.getfa(x)]+outdata); if(op[2]=='3')printf("%d\n",out.val[root]+outdata); } if(op[1]=='U') { scanf("%d%d",&x,&y); x=in.getfa(x);y=in.getfa(y); if(x==y)continue; int temp=in.merge(x,y); if(temp==x)root=out.delet(y); else root=out.delet(x); } } return 0; }