棘手的操作
题目描述
有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，输出对应的结果，每个结果占一行。
输入输出样例
说明
对于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 ",T.val[x]+allsign+T.sum(x)); break; case '2': read(x); printf("%d ",T.val[T.find(x)]+allsign); break; case '3': printf("%d ",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; }