[SCOI2011]棘手的操作

题目描述

有N个节点，标号从1到N，这N个节点一开始相互不连通。第i个节点的初始权值为a[i]，接下来有如下一些操作：U x y: 加一条边，连接第x个节点和第y个节点A1 x v: 将第x个节点的权值增加vA2 x v: 将第x个节点所在的连通块的所有节点的权值都增加vA3 v: 将所有节点的权值都增加vF1 x: 输出第x个节点当前的权值F2 x: 输出第x个节点所在的连通块中，权值最大的节点的权值F3: 输出所有节点中，权值最大的节点的权值

输入输出格式

输入格式：

输入的第一行是一个整数N，代表节点个数。接下来一行输入N个整数，a[1], a[2], ..., a[N]，代表N个节点的初始权值。再下一行输入一个整数Q，代表接下来的操作数。最后输入Q行，每行的格式如题目描述所示。

输出格式：

对于操作F1, F2, F3，输出对应的结果，每个结果占一行。

输入输出样例

输入样例#1：

输出样例#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

用两颗左偏树来维护这些棘手的操作

一个维护每个堆,一个维护全局最大值.

U:将x,y所处的两个堆合并,合并的时候记得down.

A1:把这个点的堆顶从第二个堆中删除,然后把这个点从第一个堆中删除,+v之后插入,堆顶也要插入.

A2:将堆顶打上标记,并从第二个堆中取出,+v后插入第二个堆.

A3:用一个全局变量即可

F1:把他上面的节点全部下放后直接查询

F2:直接查询这个堆的堆顶

F3:直接查询第二个堆的堆顶.

代码有点难写…

  1 #include<bits/stdc++.h>
  2 #define maxn 300010
  3 using namespace std;
  4 char S[3];
  5 multiset<int>st;
  6 int key[maxn],ls[maxn],rs[maxn],fa[maxn],lazy[maxn],d[maxn],q[maxn],atag=0;
  7 int sp[maxn*2],l[maxn*2],r[maxn*2],dd[maxn*2],val[maxn*2],faa[maxn*2],rt=0,tt=0;
  8 int Find(int x){//不能路径压缩.
  9   while(fa[x]) x=fa[x];
 10   return x;
 11 }
 12 int Find2(int x){
 13   while(faa[x]) x=faa[x];
 14   return x;
 15 }
 16 inline void down(int x){
 17   if(!lazy[x])return;
 18   int t=lazy[x];lazy[x]=0;
 19   if(ls[x])key[ls[x]]+=t,lazy[ls[x]]+=t;
 20   if(rs[x])key[rs[x]]+=t,lazy[rs[x]]+=t;
 21 }
 22 void pd(int x){
 23   int tot=0;
 24   while(x)q[++tot]=x,x=fa[x];
 25   while(tot)down(q[tot--]);
 26 }
 27 int unionn(int x,int y){
 28   if(!x) return y;
 29   if(!y) return x;
 30   if(key[x]<key[y]) swap(x,y);
 31   down(x);
 32   rs[x]=unionn(rs[x],y);
 33   fa[rs[x]]=x;
 34   if(d[rs[x]]>d[ls[x]])
 35     swap(rs[x],ls[x]);
 36   d[x]=d[rs[x]]+1;
 37   return x;
 38 }
 39 int unionn2(int x,int y){
 40   if(!x) return y;
 41   if(!y) return x;
 42   if(val[x]<val[y]) swap(x,y);
 43   r[x]=unionn2(r[x],y);
 44   faa[r[x]]=x;
 45   if(dd[r[x]]>dd[l[x]])
 46     swap(r[x],l[x]);
 47   dd[x]=dd[r[x]]+1;
 48   return x;
 49 }
 50 inline void newnode(int keyy,int p){
 51   ++tt;
 52   val[tt]=keyy;
 53   sp[p]=tt;
 54   if(!rt) rt=tt;
 55   else rt=unionn2(rt,tt);
 56 }
 57 inline void erase(int x){
 58   int t=unionn2(l[x],r[x]),f=faa[x];
 59   l[x]=r[x]=0,faa[x]=0;
 60   if(x==l[f])l[f]=t;
 61   else r[f]=t;
 62   faa[t]=f;
 63   rt=Find2(t);
 64 }
 65 int del(int x){
 66   pd(x);
 67   int t=unionn(ls[x],rs[x]),f=fa[x];
 68   ls[x]=rs[x]=0,fa[x]=0;
 69   if(x==ls[f])ls[f]=t;
 70   else rs[f]=t;
 71   fa[t]=f;
 72   return Find(t);
 73 }
 74 inline void Add(int x,int v){
 75   pd(x);
 76   erase(sp[Find(x)]);
 77   key[x]+=v;
 78   int t=unionn(x,del(x));
 79   newnode(key[t],t);
 80 }
 81 inline void Add2(int x,int v){
 82   int t=Find(x);
 83   lazy[t]+=v;
 84   erase(sp[t]);
 85   key[t]+=v;
 86   newnode(key[t],t);
 87 }
 88 inline void query(int x){
 89   pd(x);
 90   printf("%d
",key[x]+atag);
 91 }
 92 inline void query2(int x){
 93   printf("%d
",key[Find(x)]+atag);
 94 }
 95 int main(){
 96   int n,m,x,y;
 97   scanf("%d",&n);
 98   for(int i=1;i<=n;i++)
 99     scanf("%d",&key[i]),newnode(key[i],i);
100   scanf("%d",&m);
101   for(int i=1;i<=m;i++){
102     scanf("%s",S);
103     if(S[0]=='U'){
104       scanf("%d%d",&x,&y);
105       int u=Find(x),v=Find(y);
106       if(u!=v){
107     if(unionn(u,v)==u)erase(sp[v]);
108     else erase(sp[u]);
109       }
110     }
111     if(S[0]=='A'){
112       if(S[1]=='1')scanf("%d%d",&x,&y),Add(x,y);
113       if(S[1]=='2')scanf("%d%d",&x,&y),Add2(x,y);
114       if(S[1]=='3')scanf("%d",&x),atag+=x;
115     }
116     if(S[0]=='F'){
117       if(S[1]=='1')scanf("%d",&x),query(x);
118       if(S[1]=='2')scanf("%d",&x),query2(x);
119       if(S[1]=='3') printf("%d
",val[rt]+atag);
120     }
121   }
122   return 0;
123 }