2333: [SCOI2011]棘手的操作

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 1979  Solved: 772

[][][]

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

 

Source

---

可并堆真是个玄学的东西我不玩了！！！

复杂度怎么分析怎么不对啊，怎么可以像平衡树那样打标记呢？

并且怎么写怎么不对........

最后无奈照黄学长抄了个代码，内层左偏树或者斜堆都可以，外层set必须用s.erase(s.find(v))

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;#define lc t[x].l#define rc t[x].rtypedef long long ll;const int N=3e5+5,INF=1e9;inline int read(){    char c=getchar();int x=0,f=1;    while(c<'0'||c>'9'){
    if(c=='-')f=-1; c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}    return x*f;}int n,Q,x,y,v;char s[20]; struct node{    int l,r,fa,v,add;}t[N];inline int find(int x){    while(t[x].fa) x=t[x].fa;    return x;}inline void pushDown(int x){    if(t[x].add){        if(lc) t[lc].v+=t[x].add,t[lc].add+=t[x].add;        if(rc) t[rc].v+=t[x].add,t[rc].add+=t[x].add;        t[x].add=0;    }}int st[N];inline void PD(int x){    while(x) st[++st[0]]=x,x=t[x].fa;    while(st[0]) pushDown(st[st[0]--]);}inline int Top(int x){    return t[find(x)].v;}int Merge(int x,int y){    if(x==0||y==0) return x+y;    if(t[x].v
           

S;inline void erase(int v){ S.erase(S.find(v));} inline void U(int x,int y){ x=find(x);y=find(y); if(x!=y){ if(Merge(x,y)==x) erase(t[y].v); else erase(t[x].v); }}inline void A1(int x,int v){ PD(x); erase(t[find(x)].v); t[x].v+=v; S.insert(t[Merge(Del(x),x)].v);}inline void A2(int x,int v){ int f=find(x); erase(t[f].v); t[f].add+=v;t[f].v+=v; S.insert(t[f].v);}int ADD;inline void F1(int x){ PD(x); printf("%d\n",t[x].v+ADD);}int main(){ //freopen("in.txt","r",stdin); n=read(); for(int i=1;i<=n;i++){ t[i].v=read(); S.insert(t[i].v); } Q=read(); while(Q--){ scanf("%s",s); if(s[0]=='U') x=read(),y=read(),U(x,y); if(s[0]=='A'){ x=read(); if(s[1]=='1') v=read(),A1(x,v); if(s[1]=='2') v=read(),A2(x,v); if(s[1]=='3') ADD+=x; } if(s[0]=='F'){ if(s[1]=='1') x=read(),F1(x); if(s[1]=='2') x=read(),printf("%d\n",t[find(x)].v+ADD); if(s[1]=='3') printf("%d\n",*--S.end()+ADD); } }}

下面是当时写了一个下午的WA代码