[bzoj2333] [SCOI2011]棘手的操作 (可并堆)

//以后为了凑字数还是把题面搬上来吧2333

发布时间果然各种应景。。。

Time Limit: 10 Sec Memory Limit: 128 MB

Description

有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: 输出所有节点中，权值最大的节点的权值

Input

输入的第一行是一个整数N，代表节点个数。

接下来一行输入N个整数，a[1], a[2], …, a[N]，代表N个节点的初始权值。

再下一行输入一个整数Q，代表接下来的操作数。

最后输入Q行，每行的格式如题目描述所示。

Output

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

Sample Input

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

Sample Output

-10
10
10

HINT

对于30%的数据，保证 N<=100，Q<=10000

对于80%的数据，保证 N<=100000，Q<=100000

对于100%的数据，保证 N<=300000，Q<=300000

对于所有的数据，保证输入合法，并且 -1000<=v, a[1], a[2], …, a[N]<=1000

看到题号就2333了。。。然而被坑了一下午T_T。。。

因为操作里有合并和查询最大值，所以显然可并堆？

要用两个可并堆，一个维护各个联通块的最大值，另一个就是节点的修改查询blabla（维护联通块的那个可以善用stl。。。跪烂）。。。。

这题还有对整个联通块的增加的操作，所以我们可以打lazy标记。。

U操作的时候，如果两个节点不在同一联通块的话，把它们合并到一起，注意到合并后少了一个联通块（堆顶值较小的那个），要在维护联通块的可并堆里面删除；同时在合并的时候要下传标记。

A1操作，把x节点的值增加以后可能会破坏最大堆的性质，一种方法是修改堆节点的姿势，不断判断是否要和父亲交换；另一种是利用可并堆性质，先删除原来的x节点，增加以后再插进去。。。（显然第二种好写得多吧）。。当然了不管是哪一种姿势都要记得先把x节点还有祖先的标记下传。

然而一个令人悲伤的消息是第一种写法还要考虑负数的情况T_T，增加的值为负数的时候就是看和那个儿子交换了。。。

A2操作，在x节点所在联通块的堆顶元素打一个懒标记；

A3操作开一个全局变量存就好了= =

F1操作，因为x节点的祖先可能有标记，所以要先把x节点的所有祖先从上到下依次下传标记，这样才能得到x节点真实的值；

F2操作，直接输出所在联通块的堆顶元素就好了；

F3操作，输出维护各个联通块的可并堆顶的值。

蒟蒻一开始用左偏树的时候删除节点还要维护距离各种蛋疼。。还写挂调了半天，换成斜堆立马过。。。

斜堆代码：

  1 #include<cstdio>
  2 #include<math.h>
  3 #include<iostream>
  4 #include<algorithm>
  5 #include<queue>
  6 #include<cstring>
  7 using namespace std;
  8 const int maxn=302333;
  9 struct zs1{
 10     int c[2],/*dis,*/val,fa;
 11     int add;
 12 }tree[maxn];
 13 struct zs2{
 14     int c[2],val,fa;
 15     //dis,
 16 }tree1[maxn];
 17 int i,j,k,n,m,alladd,x,y,q,root1,tmpp;
 18 int stack[maxn];
 19 char id[2333];
 20 
 21 int getroot(int x){
 22     while(tree[x].fa)x=tree[x].fa;return x;
 23 }
 24 void pushdown(int x){
 25     if(tree[x].add==0)return;
 26     int l=tree[x].c[0],r=tree[x].c[1],add=tree[x].add;
 27     if(l)tree[l].add+=add,tree[l].val+=add;
 28     if(r)tree[r].add+=add,tree[r].val+=add;
 29     tree[x].add=0;
 30 }
 31 void pushalldown(int x){
 32     int top=0;
 33     while(x)stack[++top]=x,x=tree[x].fa;
 34     for(;top;top--)pushdown(stack[top]);
 35 }
 36 int merge1(int a,int b){
 37     if(a==0||b==0)return a+b;
 38     if(tree1[a].val<tree1[b].val)swap(a,b);
 39     tree1[a].c[1]=merge1(tree1[a].c[1],b);
 40     int l=tree1[a].c[0],r=tree1[a].c[1];
 41     tree1[r].fa=a;
 42     swap(tree1[a].c[0],tree1[a].c[1]);
 43     return a;
 44 }
 45 void del1(int x){
 46     int fa=tree1[x].fa,newson=merge1(tree1[x].c[0],tree1[x].c[1]);
 47     tree1[x].fa=tree1[x].c[0]=tree1[x].c[1]=0;
 48     if(newson)tree1[newson].fa=fa;
 49     tree1[fa].c[tree1[fa].c[1]==x]=newson;
 50     if(!fa)root1=newson;
 51 }
 52 int merge(int a,int b){
 53     if(a==0||b==0)return a+b;
 54     if(tree[a].val<tree[b].val)swap(a,b);
 55     pushdown(a);
 56     tree[a].c[1]=merge(tree[a].c[1],b);
 57     int l=tree[a].c[0],r=tree[a].c[1];
 58     tree[r].fa=a;
 59     swap(tree[a].c[0],tree[a].c[1]);
 60     return a;
 61 }
 62 void del(int x){
 63     pushalldown(x);
 64     int newson=merge(tree[x].c[0],tree[x].c[1]),fa=tree[x].fa;
 65     tree[x].c[0]=tree[x].c[1]=tree[x].fa=0;
 66     if(newson)tree[newson].fa=fa;
 67     tree[fa].c[tree[fa].c[1]==x]=newson;
 68     if(fa)tmpp=getroot(fa);else tmpp=getroot(newson);
 69 }
 70 void runA1(int x,int v){
 71     pushalldown(x);
 72     int preroot=getroot(x);
 73     int fa=tree[x].fa;
 74     del(x);
 75     tree[x].val+=v;
 76     merge(tmpp,x);
 77     int nowroot=getroot(x);
 78     if(nowroot!=preroot||fa==0){
 79         del1(preroot);
 80         tree1[nowroot].val=tree[nowroot].val;
 81         root1=merge1(root1,nowroot);
 82     }
 83 }
 84 void runA2(int x,int y){
 85     x=getroot(x);
 86     tree[x].add+=y;tree[x].val+=y;
 87     del1(x);
 88     tree1[x].val=tree[x].val;
 89     root1=merge1(root1,x);
 90 }
 91 void runU(int x,int y){
 92     int t[2];
 93     t[0]=getroot(x);t[1]=getroot(y);
 94     if(t[0]!=t[1])
 95         del1(t[t[0]==merge(t[0],t[1])]);
 96 }
 97 int main(){
 98     tree[0].val=-1233333333;
 99     scanf("%d",&n);
100     for(i=1;i<=n;i++)scanf("%d",&tree[i].val),tree1[i].val=tree[i].val;
101     for(i=1;i<=n;i++)root1=merge1(root1,i);
102     scanf("%d",&q);
103     while(q--){
104         scanf("%s",id);
105         if(id[0]=='U'){
106             scanf("%d%d",&x,&y);
107             runU(x,y);
108         }else
109         if(id[0]=='A'){
110             scanf("%d",&x);if(id[1]!='3')scanf("%d",&y);
111             if(id[1]=='1')runA1(x,y);
112             if(id[1]=='2')runA2(x,y);
113             if(id[1]=='3')alladd+=x;
114         }else
115         if(id[0]=='F'){
116             if(id[1]!='3')scanf("%d",&x);
117             if(id[1]=='1'){
118                 pushalldown(x);
119                 printf("%d
",tree[x].val+alladd);
120             }
121             if(id[1]=='2')printf("%d
",tree[getroot(x)].val+alladd);
122             if(id[1]=='3')printf("%d
",tree1[root1].val+alladd);
123         }
124     }
125     return 0;
126 }

View Code

左偏树（其实只有几行不一样= =）：

  1 #include<cstdio>
  2 #include<math.h>
  3 #include<iostream>
  4 #include<algorithm>
  5 #include<queue>
  6 #include<cstring>
  7 using namespace std;
  8 const int maxn=302333;
  9 struct zs1{
 10     int c[2],dis,val,fa;
 11     int add;
 12 }tree[maxn];
 13 struct zs2{
 14     int c[2],dis,val,fa;
 15 }tree1[maxn];
 16 int i,j,k,n,m,alladd,x,y,q,root1,tmpp;
 17 int stack[maxn];
 18 char id[2333];
 19 
 20 int getroot(int x){
 21     while(tree[x].fa)x=tree[x].fa;return x;
 22 }
 23 void pushdown(int x){
 24     if(tree[x].add==0)return;
 25     int l=tree[x].c[0],r=tree[x].c[1],add=tree[x].add;
 26     if(l)tree[l].add+=add,tree[l].val+=add;
 27     if(r)tree[r].add+=add,tree[r].val+=add;
 28     tree[x].add=0;
 29 }
 30 void pushalldown(int x){
 31     int top=0;
 32     while(x)stack[++top]=x,x=tree[x].fa;
 33     for(;top;top--)pushdown(stack[top]);
 34 }
 35 int merge1(int a,int b){
 36     if(a==0||b==0)return a+b;
 37     if(tree1[a].val<tree1[b].val)swap(a,b);
 38     tree1[a].c[1]=merge1(tree1[a].c[1],b);
 39     int l=tree1[a].c[0],r=tree1[a].c[1];
 40     tree1[r].fa=a;
 41     if(tree1[l].dis<tree1[r].dis)swap(tree1[a].c[0],tree1[a].c[1]);
 42     tree1[a].dis=tree1[r].dis+1;
 43     return a;
 44 }
 45 void del1(int x){
 46     int fa=tree1[x].fa,newson=merge1(tree1[x].c[0],tree1[x].c[1]);
 47     tree1[x].fa=tree1[x].c[0]=tree1[x].c[1]=0;
 48     if(newson)tree1[newson].fa=fa;
 49     if(fa){
 50         tree1[fa].c[tree1[fa].c[1]==x]=newson;
 51         while(fa){
 52             int pre=tree1[fa].dis;
 53             if(tree1[tree1[fa].c[1]].dis>tree1[tree1[fa].c[0]].dis)swap(tree1[fa].c[0],tree1[fa].c[1]);
 54             tree1[fa].dis=tree1[tree1[fa].c[1]].dis+1;
 55             if(tree1[fa].dis==pre)break;
 56             fa=tree1[fa].fa;
 57         }
 58     }
 59     else root1=newson;
 60 }
 61 int merge(int a,int b){
 62     if(a==0||b==0)return a+b;
 63     if(tree[a].val<tree[b].val)swap(a,b);
 64     pushdown(a);
 65     tree[a].c[1]=merge(tree[a].c[1],b);
 66     int l=tree[a].c[0],r=tree[a].c[1];
 67     tree[r].fa=a;
 68     if(tree[l].dis<tree[r].dis)swap(tree[a].c[0],tree[a].c[1]);
 69     tree[a].dis=tree[tree[a].c[1]].dis+1;
 70     return a;
 71 }
 72 void del(int x){
 73     pushalldown(x);
 74     int newson=merge(tree[x].c[0],tree[x].c[1]),fa=tree[x].fa;
 75     tree[x].c[0]=tree[x].c[1]=tree[x].fa=0;
 76     if(newson)tree[newson].fa=fa;
 77     if(!fa)tmpp=getroot(newson);else tmpp=getroot(fa);
 78     if(fa){
 79         tree[fa].c[tree[fa].c[1]==x]=newson;
 80         while(fa&&tree[fa].c[1]){
 81             int pre=tree[fa].dis;
 82             if(tree[tree[fa].c[1]].dis>tree[tree[fa].c[0]].dis)swap(tree[fa].c[0],tree[fa].c[1]);
 83             tree[fa].dis=tree[tree[fa].c[1]].dis+1;
 84             if(tree[fa].dis==pre)break;
 85             fa=tree[fa].fa;
 86         }
 87     }
 88     //if(newson)tmpp=getroot(newson);
 89     //else tmpp=getroot(fa);//这里是错的，如果维护距离的时候fa跑到了0节点就会挂TAT 
 90 }
 91 void runA1(int x,int v){
 92     pushalldown(x);
 93     int preroot=getroot(x);
 94     int fa=tree[x].fa;
 95     del(x);
 96     tree[x].val+=v;
 97     merge(tmpp,x);
 98     int nowroot=getroot(x);
 99     if(nowroot!=preroot||fa==0){
100         del1(preroot);
101         tree1[nowroot].val=tree[nowroot].val;
102         root1=merge1(root1,nowroot);
103     }
104 }
105 void runU(int x,int y){
106     int t[2];
107     t[0]=getroot(x);t[1]=getroot(y);
108     if(t[0]!=t[1])
109         del1(t[t[0]==merge(t[0],t[1])]);
110 }
111 void runA2(int x,int y){
112     x=getroot(x);
113     tree[x].add+=y;tree[x].val+=y;
114     del1(x);
115     tree1[x].val=tree[x].val;
116     root1=merge1(root1,x);
117 }
118 int main(){
119     tree[0].dis=tree1[0].dis=-1;
120     tree[0].val=-1233333333;
121     scanf("%d",&n);
122     for(i=1;i<=n;i++)scanf("%d",&tree[i].val),tree1[i].val=tree[i].val;
123     for(i=1;i<=n;i++)root1=merge1(root1,i);
124     scanf("%d",&q);
125     while(q--){
126         scanf("%s",id);
127         if(id[0]=='U'){
128             scanf("%d%d",&x,&y);
129             runU(x,y);
130         }else
131         if(id[0]=='A'){
132             scanf("%d",&x);if(id[1]!='3')scanf("%d",&y);
133             if(id[1]=='1')runA1(x,y);
134             if(id[1]=='2')runA2(x,y);
135             if(id[1]=='3')alladd+=x;
136         }else
137         if(id[0]=='F'){
138             if(id[1]!='3')scanf("%d",&x);
139             if(id[1]=='1'){
140                 pushalldown(x);
141                 printf("%d
",tree[x].val+alladd);
142             }
143             if(id[1]=='2')printf("%d
",tree[getroot(x)].val+alladd);
144             if(id[1]=='3')printf("%d
",tree1[root1].val+alladd);
145         }
146     }
147     return 0;
148 }

View Code

最近几道可并堆用斜堆和左偏树似乎毫无差异。。。斜堆大法好！