2333: [SCOI2011]棘手的操作[写不出来]

2333: [SCOI2011]棘手的操作

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 1979 Solved: 772
[Submit][Status][Discuss]

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

0 0 0

A1 3 -20

A1 2 20

U 1 3

A2 1 10

F1 3

F2 3

A3 -10

Sample Output

-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

Day2

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

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

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

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

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <set>

using namespace std;

#define lc t[x].l

#define rc t[x].r

typedef long long ll;

const int N=3e5+,INF=1e9;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-; c=getchar();}

    while(c>=''&&c<=''){x=x*+c-''; c=getchar();}

    return x*f;

}

int n,Q,x,y,v;

char s[];

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=;

    }

}

int st[N];

inline void PD(int x){

    while(x) st[++st[]]=x,x=t[x].fa;

    while(st[]) pushDown(st[st[]--]);

}

inline int Top(int x){

    return t[find(x)].v;

}

int Merge(int x,int y){

    if(x==||y==) return x+y;

    if(t[x].v<t[y].v) swap(x,y);

    pushDown(x);

    rc=Merge(rc,y);

    t[rc].fa=x;

    swap(lc,rc);

    return x;

}

int Del(int x){

    pushDown(x);//no

    int f=t[x].fa,y=Merge(lc,rc);

    t[y].fa=f;

    if(t[f].l==x) t[f].l=y;

    else t[f].r=y;

    t[x].l=t[x].r=t[x].fa=;

    return find(y);

}

multiset<int> 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=;i<=n;i++){

        t[i].v=read();

        S.insert(t[i].v);

    }

    Q=read();

    while(Q--){

        scanf("%s",s);

        if(s[]=='U') x=read(),y=read(),U(x,y);

        if(s[]=='A'){

            x=read();

            if(s[]=='') v=read(),A1(x,v);

            if(s[]=='') v=read(),A2(x,v);

            if(s[]=='') ADD+=x;

        }

        if(s[]=='F'){

            if(s[]=='') x=read(),F1(x);

            if(s[]=='') x=read(),printf("%d\n",t[find(x)].v+ADD);

            if(s[]=='') printf("%d\n",*--S.end()+ADD);

        }

    }

}

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

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

#define lc t[x].l

#define rc t[x].r

typedef long long ll;

const int N=3e5+,INF=1e9;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-; c=getchar();}

    while(c>=''&&c<=''){x=x*+c-''; c=getchar();}

    return x*f;

}

int n,Q,x,y,v;

char s[];

int fa[N];

inline int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}

struct node{

    int l,r,fa,v,d,size;

}t[N];

int add[N];

//inline void update(int x){t[x].size=t[lc].size+t[rc].size+1;}

void Add(int x,int v){

    t[x].v+=v;

    if(lc) Add(lc,v);

    if(rc) Add(rc,v);

}

int Merge(int x,int y){//printf("Merge %d %d\n",x,y);

    if(x==||y==) return x+y;

    if(t[x].v<t[y].v) swap(x,y);

    rc=Merge(rc,y);

//  update(x);printf("MS %d %d\n",x,t[x].size);

    t[rc].fa=x;

    if(t[lc].d<t[rc].d) swap(lc,rc);

    t[x].d=t[rc].d+;

    return x;

}

int Del(int x){

    int f=t[x].fa,y=Merge(lc,rc);

    t[y].fa=f;

    if(f&&t[f].l==x) t[f].l=y;

    if(f&&t[f].r==x) t[f].r=y;

//  update(f);

    int re=f?find(f):y;

    t[x].l=t[x].r=t[x].fa=t[x].d=;

    x=f;

    while(x){

        if(t[lc].d<t[rc].d) swap(lc,rc);

        if(t[rc].d+==t[x].d) break;

        t[x].d=t[rc].d+;

        x=t[x].fa;

    }

    return re;

}

namespace S{

struct node{

    int l,r,fa,v,d;

}t[N];

int root;

int Merge(int x,int y){//printf("Merge %d %d\n",x,y);

    if(x==||y==) return x+y;

    if(t[x].v<t[y].v) swap(x,y);

    rc=Merge(rc,y);

    t[rc].fa=x;

    if(t[lc].d<t[rc].d) swap(lc,rc);

    t[x].d=t[rc].d+;

    return x;

}

int Del(int x){

    int f=t[x].fa,y=Merge(lc,rc);

    t[y].fa=f;

    if(f&&t[f].l==x) t[f].l=y;

    if(f&&t[f].r==x) t[f].r=y;

    int re=f?find(f):y;

    t[x].l=t[x].r=t[x].fa=t[x].d=;

    x=f;

    while(x){

        if(t[lc].d<t[rc].d) swap(lc,rc);

        if(t[rc].d+==t[x].d) break;

        t[x].d=t[rc].d+;

        x=t[x].fa;

    }//printf("DElre %d\n",re);

    return re;

}

int q[N],head,tail;

inline void lop(int &x){if(x==N) x=;}

void Heapify(){

    head=tail=;

    for(int i=;i<=n;i++) q[tail++]=i;

    int x,y,z;

    while(head!=tail){

        x=q[head++];lop(head);

        if(head!=tail) y=q[head++],lop(head);

        else break;

        z=Merge(x,y);

        q[tail++]=z;lop(tail);

    }

    root=x;

}

}

inline void U(int x,int y){

    x=find(x);y=find(y);

    if(x!=y){

        S::Del(x);

        S::Del(y);//printf("IWantToSeeSize %d %d\n",t[x].size,t[y].size);

        if(t[x].size>t[y].size) swap(x,y);

        Add(x,add[x]-add[y]);

        int z=fa[x]=fa[y]=Merge(x,y);//printf("M %d %d %d %d %d %d\n",x,y,z,t[x].v,t[y].v,t[z].v);

        add[z]=add[y];//printf("hiz %d %d %d %d\n",z,S::t[z].v,S::root,S::t[S::root].v);

        t[z].size=t[x].size+t[y].size;

        S::root=S::Merge(S::root,z);//printf("hiroot %d %d\n",S::root,S::t[S::root].v);

    }

}

inline void A1(int x,int v){

    int fx=find(x);

    S::root=S::Del(fx);

    int _add=add[fx],_size=t[fx].size;

    int y=Del(x);

    t[x].v+=v;//printf("what %d %d\n",x,y);

    int z=fa[x]=fa[y]=Merge(x,y);

    //printf("A1 %d %d %d\nAS %d %d %d\n",x,y,z,t[x].size,t[y].size,t[z].size);

    add[z]=_add;t[z].size=_size;

    S::t[z].v=t[z].v+add[z];

    S::root=Merge(S::root,z);

}

inline void A2(int x,int v){

    x=find(x);

    S::root=S::Del(x);

    add[x]+=v;

    S::t[x].v=t[x].v+add[x];

    S::root=Merge(S::root,x);

}

int ADD;

inline void A3(int v){ADD+=v;}

inline void F1(int x){

    int fx=find(x);

    printf("%d\n",t[x].v+add[fx]+ADD);

}

inline void F2(int x){

    int fx=find(x);

    printf("%d\n",t[fx].v+add[fx]+ADD);

}

inline void F3(){printf("%d\n",S::t[S::root].v+ADD);}

int main(){

    //freopen("in.txt","r",stdin);

    n=read();

    for(int i=;i<=n;i++){

        t[i].v=S::t[i].v=read();

        t[i].size=; fa[i]=i;

    }

    t[].d=S::t[].d=-;

    S::Heapify();

    Q=read();//printf("BEGIN\n");

    while(Q--){ //printf("QQQQQQQQQ %d\n",Q);

        scanf("%s",s);

        if(s[]=='U') x=read(),y=read(),U(x,y);

        if(s[]=='A'){

            x=read();

            if(s[]=='') v=read(),A1(x,v);

            if(s[]=='') v=read(),A2(x,v);

            if(s[]=='') A3(x);

        }

        if(s[]=='F'){

            if(s[]=='') x=read(),F1(x);

            if(s[]=='') x=read(),F2(x);

            if(s[]=='') F3();

        }

    }

}

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <set>

using namespace std;

#define lc t[x].l

#define rc t[x].r

typedef long long ll;

const int N=3e5+,INF=1e9;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-; c=getchar();}

    while(c>=''&&c<=''){x=x*+c-''; c=getchar();}

    return x*f;

}

int n,Q,x,y,v;

char s[];

struct node{

    int l,r,fa,v,d,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;

        if(rc) t[rc].v+=t[x].add;

        t[x].add=;

    }

}

int st[N],top;

inline void PD(int x){

    while(x) st[++top]=x,x=t[x].fa;

    while(top) pushDown(st[top--]);

}

int Merge(int x,int y){

    if(x==||y==) return x+y;

    if(t[x].v<t[y].v) swap(x,y);

    pushDown(x);

    rc=Merge(rc,y);

    t[rc].fa=x;

    if(t[lc].d<t[rc].d) swap(lc,rc);

    t[x].d=t[rc].d+;

    return x;

}

int Del(int x){

    pushDown(x);

    int f=t[x].fa,y=Merge(lc,rc);

    t[y].fa=f;

    if(f&&t[f].l==x) t[f].l=y;

    if(f&&t[f].r==x) t[f].r=y;

    t[x].l=t[x].r=t[x].fa=t[x].d=;

    x=f;

    while(x){

        if(t[lc].d<t[rc].d) swap(lc,rc);

        if(t[rc].d+==t[x].d) break;

        t[x].d=t[rc].d+;

        x=t[x].fa;

    }

    return find(y);

}

multiset<int> S;

inline void U(int x,int y){

    x=find(x);y=find(y);

    if(x!=y){

        if(Merge(x,y)==x) S.erase(t[y].v);

        else S.erase(t[x].v);

    }

}

inline void A1(int x,int v){

    PD(x);

    S.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);

    S.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=;i<=n;i++){

        t[i].v=read();

        S.insert(t[i].v);

    }

    t[].d=-;

    Q=read();

    while(Q--){

        scanf("%s",s);

        if(s[]=='U') x=read(),y=read(),U(x,y);

        if(s[]=='A'){

            x=read();

            if(s[]=='') v=read(),A1(x,v);

            if(s[]=='') v=read(),A2(x,v);

            if(s[]=='') ADD+=x;

        }

        if(s[]=='F'){

            if(s[]=='') x=read(),F1(x);

            if(s[]=='') x=read(),printf("%d\n",t[find(x)].v+ADD);

            if(s[]=='') printf("%d\n",*--S.end()+ADD);

        }

    }

}

巴特西

2333: [SCOI2011]棘手的操作[写不出来]