2333: [SCOI2011]棘手的操作

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 2538  Solved: 986

[][][]

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

 

支持合并操作，修改操作，可以用可并堆；

  这个既要维护图的最大值，又要维护全局的最大值，全局的最大值就是每个块的最大值，那么就可以把这些块的最大值抠出来放到这个堆中维护； h1为连通块的堆，h2为全局最大值的堆。

  在斜堆里增加几个操作：

1.find(x) 找到x的祖先（堆顶），这个直接暴力跳；

2.Down(x) 涉及到整块修改，lz数组，与线段树写法一样；

3.del(x)  先下放，合并左右儿子，更新父子关系，返回新的堆顶；合并时特判，如果修改的是根，则要更新根的值；

4.Sum(x) ：由于祖先节点中的lazy没有全部下放，所以在查询的时候要统计祖先的lazy；直接暴力跳就行，大概深度为log(n)；

5.Newnode(x,v) .......=0;v[x]=vv; 新建节点，不用在操作里写很多特判；

对于每个操作

  对于A1：单点修改  ， 修改后会改变位置，先将x的祖先在h2中删除，在把x在h1

中删除，把值统计好后，再合并h1与当前点；在合并h2与此时堆中的最大值；

  对于A2：删除h2中的x所在根的这个节点；newnode后合并；对于h1，lz一下；

  对于A3：直接设全局变量all

  对于F1 ： 当前值 + 祖先ly + 全局all

  对于F2　：　祖先值 +　全局all

  对于 F3： printf(“%d”,h2.v[h2.rt]+all);

1 #include
      
         2 #define re register  3 #define il inline  4 #define rep(i,a,b) for(register int i=a;i<=b;++i)  5 #define file(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);  6 using namespace std;  7 const int N=300020;  8 int all,n;  9 struct M_heap{ 10     int l[N],r[N],v[N],lz[N],fa[N]; 11     int rt; 12     il int find(int x){ 13         while(fa[x]&&fa[x]!=x) x=fa[x]; 14         return x; 15     } 16     il void newnode(int x,int vv){ 17         fa[x]=l[x]=r[x]=v[x]=lz[x]=0; 18         v[x]=vv; 19     } 20     il int sum(int x){ 21         re int res=0; 22         while(fa[x]) res+=lz[fa[x]],x=fa[x]; 23         return res; 24     } 25     il void down(int x){ 26         v[l[x]]+=lz[x],v[r[x]]+=lz[x]; 27         lz[l[x]]+=lz[x],lz[r[x]]+=lz[x]; 28         lz[x]=0; 29     } 30     il int merge(int x,int y){ 31         if(x==0||y==0) return x+y; 32         if(v[x]
       
        '9')&&ch!='-') ch=getchar(); 53     if(ch=='-') f=-1,ch=getchar(); 54     while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar(); 55     return res*f; 56 } 57 il void U(){ 58     re int x=gi(),y=gi(); 59     x=h1.find(x),y=h1.find(y); 60     if(x==y) return; 61     if(h1.merge(x,y)==x) h2.del(y); 62     else h2.del(x); 63 } 64 il void A1(){ 65     re int x=gi(),v=gi(); 66     h2.del(h1.find(x)); 67     int y=h1.del(x); 68     h1.newnode(x,v+h1.v[x]+h1.sum(x)); 69     re int now=h1.merge(x,y); 70     h2.newnode(now,h1.v[now]); 71     h2.rt=h2.merge(h2.rt,now); 72 } 73 il void A2(){ 74     re int x=gi(),v=gi(); 75     x=h1.find(x); 76     h1.v[x]+=v;h1.lz[x]+=v; 77     h2.del(x); 78     h2.newnode(x,h1.v[x]); 79     h2.rt=h2.merge(h2.rt,x); 80 } 81 il void A3() {all+=gi();} 82 il void F1(){ 83     re int x=gi(); 84     printf("%d\n",h1.v[x]+h1.sum(x)+all); 85     return; 86 } 87 il void F2(){ 88     re int x=gi(); 89     x=h1.find(x); 90     printf("%d\n",h1.v[x]+all); 91 } 92 il void F3(){ 93     printf("%d\n",h2.v[h2.rt]+all); 94     return; 95 } 96 int main(){ 97     file("heap"); 98     n=gi(); 99     re int u;100     rep(i,1,n){101         u=gi();h1.v[i]=h2.v[i]=u;102     }103     h2.rt=1;104     for(re int i=2;i<=n;i++) h2.rt=h2.merge(h2.rt,i);105     re int Q=gi(); char ch[4];106     while(Q--){107         scanf("%s",ch);108         if(ch[0]=='U') U();109         else if(ch[0]=='A'){110             if(ch[1]=='1') A1();111             else if(ch[1]=='2') A2();112             else A3();113         }114         else{115             if(ch[1]=='1') F1();116             else if(ch[1]=='2') F2();117             else F3();118         }119     }120     return 0;121 }