洛谷P3273 [SCOI2011] 棘手的操作 [左偏樹]

　　題目傳送門

棘手的操作

題目描述

有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，代表節點個數。接下來一行輸入N個整數，a[1], a[2], ..., a[N]，代表N個節點的初始權值。再下一行輸入一個整數Q，代表接下來的操作數。最后輸入Q行，每行的格式如題目描述所示。

輸出格式：

對于操作F1, F2, F3，輸出對應的結果，每個結果占一行。

輸入輸出樣例

?

輸入樣例#1：?

3
0 0 0
8
A1 3 -20
A1 2 20
U 1 3
A2 1 10
F1 3
F2 3
A3 -10
F3

輸出樣例#1：?

-10
10
10

說明

對于30%的數據，保證 N<=100，Q<=10000

對于80%的數據，保證 N<=100000，Q<=100000

對于100%的數據，保證 N<=300000，Q<=300000

對于所有的數據，保證輸入合法，并且 -1000<=v, a[1], a[2], ..., a[N]<=1000

?

---

　　分析：

　　真是一道惡心的左偏樹題。

　　需要維護兩個左偏樹，第一個維護正常的操作信息，第二個維護所有點中的最大值。

　　第一種操作：在第一個左偏樹中$merge$即可，另外有一個小優化，合并的兩個堆頂中較小的一個可以直接從第二個左偏樹中刪除（正確性自己思考）。

　　第二種操作：將該點從兩個左偏樹中刪除，修改值以后再重新放回去。

　　第三種操作：用$lazy$標記，只修改堆頂的值，后面再$merge$或者刪除節點的時候下方標記。

　　第四種操作：用一個變量記錄，需要輸出的時候再加上。

　　第五種操作：直接輸出第一個左偏樹中該節點的值。

　　第六種操作：直接輸出第一個左偏樹中該節點所在堆的堆頂的值。

　　第七種操作：直接輸出第二個左偏樹的根節點的值。

　　以上。

　　題如其名，真$TM$又棘手又惡心。。。

　　Code：

?

//It is made by HolseLee on 28th Aug 2018
//Luogu.org P3273
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define Max(a,b) (a)>(b) ? (a) : (b)
using namespace std;const int N=3e5+7;
int n,a[N],m,allsign,root;
struct Leftist{int ch[N][2],val[N],sign[N],fa[N],dis[N];void clear(int x){ch[x][0]=ch[x][1]=fa[x]=0;}int sum(int x){int ret=0;while(x=fa[x])ret+=sign[x];return ret;}void pushdown(int x){int ul=ch[x][0], ur=ch[x][1];if( ul )val[ul]+=sign[x], sign[ul]+=sign[x];if( ur )val[ur]+=sign[x], sign[ur]+=sign[x];sign[x]=0;}int merge(int x,int y){if(!x||!y)return x+y;if( val[x]<val[y] )swap(x,y);pushdown(x);int &ul=ch[x][0], &ur=ch[x][1];ur=merge(ur,y); fa[ur]=x;if( dis[ur]>dis[ul] )swap(ul,ur);dis[x]=dis[ur]+1;return x;}int find(int x){while(fa[x])x=fa[x];return x;}int delet(int x){pushdown(x);int fx=fa[x];int ka=merge(ch[x][0],ch[x][1]);fa[ka]=fx;if( fx )ch[fx][x==ch[fx][1]]=ka;while( fx ) {if( dis[ch[fx][0]]<dis[ch[fx][1]] )swap(ch[fx][0],ch[fx][1]);if( dis[fx]==dis[ch[fx][1]]+1 )return root;dis[fx]=dis[ch[fx][1]]+1;ka=fx;fx=fa[fx];}return ka;}int add_point(int x,int v){int fx=find(x);if( fx==x ) {if( ch[x][0]+ch[x][1]==0 ){val[x]+=v; return x;} else {if( ch[x][0] ) fx=ch[x][0];else fx=ch[x][1];}}delet(x);val[x]+=v+sum(x);clear(x);return merge(find(fx),x);}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();}
}T,H;void read(int &x)
{x=0; char ch=getchar(); bool flag=false;while( ch<'0' || ch>'9' ) {if( ch=='-' )flag=true;ch=getchar();}while( ch>='0' && ch<='9' ) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}flag?x*=(-1):1;
}int main()
{read(n);T.dis[0]=H.dis[0]=-1;for(int i=1; i<=n; ++i){read(a[i]);T.val[i]=H.val[i]=a[i];}root=H.build();read(m);char op[3];int x,y,fx,fy,temp;for(int i=1; i<=m; ++i){scanf("%s",op);if( op[0]=='A' ) {switch( op[1] ){case '1':read(x), read(y);root=H.delet(T.find(x));temp=T.add_point(x,y);H.val[temp]=T.val[temp];H.clear(temp);root=H.merge(root,temp);break;case '2':read(x), read(y); fx=T.find(x);root=H.delet(fx);T.val[fx]+=y; T.sign[fx]+=y;H.val[fx]=T.val[fx];H.clear(fx);root=H.merge(root,fx);break;case '3':read(y);allsign+=y;break;}} else if( op[0]=='F' ) {switch( op[1] ){case '1':read(x);printf("%d\n",T.val[x]+allsign+T.sum(x));break;case '2':read(x);printf("%d\n",T.val[T.find(x)]+allsign);break;case '3':printf("%d\n",H.val[root]+allsign);break;}} else {read(x), read(y);fx=T.find(x), fy=T.find(y);if( fx==fy )continue;temp=T.merge(fx,fy);if( temp==fx )root=H.delet(fy);else root=H.delet(fx);}}return 0;
}

?