吐槽

上午风浔凌julao问我的神题

操作又多又毒瘤又棘手。。。

然后bzoj题号正好是2333，2333333333

思路

貌似只有我是这么写的

线段树合并，

每个线段树存每个连通块的信息，维护点的值，然后并查集维护。。

然后内存被卡，手写一发内存池

然后TLE了，加上O2终于过了

代码

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <stack>

using namespace std;

int fa[300010],Nodecnt,root[300010],n,q,alladd;

struct Node{

    int lson,rson;

    short maxx,tag;

}Seg[300000*25];

int pool[300000*20],top=0;

inline char Getchar() {

    static char buf[(1<<16)], *p1 = buf, *p2 = buf;

    return p1==p2&&(p2=(p1=buf)+fread(buf,1,(1<<16),stdin),p1==p2)?EOF:*p1++;

}

inline int read(){

    int x=0,f=1;

    char ch=Getchar();

    while(ch<'0'||ch>'9'){

        if(ch=='-')

            f=-1;

        ch=Getchar();

    }

    while(ch>='0'&&ch<='9'){

        x=(x<<1)+(x<<3)+(ch^48);

        ch=Getchar();

    }

    return x*f;

}

int getnew(void){

    if(top){

        int t=pool[top];

        top--;

        Seg[t].lson=Seg[t].rson=Seg[t].maxx=Seg[t].tag=0;

        return t;

    }

    return ++Nodecnt;

}

void throwin(int x){

    pool[++top]=x;

}

int find(int x){

    if(fa[x]==x)

        return x;

    else return fa[x]=find(fa[x]);

}

void pushup(int o){

    Seg[o].maxx=max(Seg[Seg[o].lson].maxx,Seg[Seg[o].rson].maxx);

}

void pushdown(int o){

    if(Seg[o].tag){

        if(Seg[o].lson){

            Seg[Seg[o].lson].tag+=Seg[o].tag;

            Seg[Seg[o].lson].maxx+=Seg[o].tag;

        }

        if(Seg[o].rson){

            Seg[Seg[o].rson].tag+=Seg[o].tag;

            Seg[Seg[o].rson].maxx+=Seg[o].tag;

        }

        Seg[o].tag=0;

    }

}

void merge(int x,int y,int l,int r,int &o){

    pushdown(x);

    pushdown(y);

    if(x*y==0){

        o=x+y;

        return;

    }

    if(l==r){

        o=getnew();

        Seg[o].maxx=max(Seg[x].maxx,Seg[y].maxx);

        throwin(x);

        throwin(y);

        return;

    }

    o=getnew();

    Seg[o].maxx=max(Seg[x].maxx,Seg[y].maxx);

    int mid=(l+r)>>1;

    merge(Seg[x].lson,Seg[y].lson,l,mid,Seg[o].lson);

    merge(Seg[x].rson,Seg[y].rson,mid+1,r,Seg[o].rson);

    throwin(x);

    throwin(y);

}

void add(int l,int r,int &o,int pos,int val){

    // printf("l=%d r=%d o=%d pos=%d val=%d\n",l,r,o,pos,val);

    if(!o)

        o=getnew();

    // printf("l=%d r=%d o=%d pos=%d val=%d\n",l,r,o,pos,val);

    if(l==r){

        Seg[o].maxx+=val;

        return;

    }

    pushdown(o);

    // printf("ok\n");

    int mid=(l+r)>>1;

    if(pos<=mid)

        add(l,mid,Seg[o].lson,pos,val);

    else

        add(mid+1,r,Seg[o].rson,pos,val);

    pushup(o);

}

void erase(int l,int r,int &o,int pos){

    pushdown(o);

    if(l==r){

        throwin(o);

        o=0;

        return;

    }

    // printf("ok\n");

    int mid=(l+r)>>1;

    if(pos<=mid){

        erase(l,mid,Seg[o].lson,pos);

        if((!Seg[o].rson)&&(!Seg[o].lson)){

            throwin(o);

            o=0;

        }

    }

    else{

        erase(mid+1,r,Seg[o].rson,pos);

        if((!Seg[o].rson)&&(!Seg[o].lson)){

            throwin(o);

            o=0;

        }

    }

    pushup(o);

}

void debug(int l,int r,int o){

    if(!o)

        return;

    printf("l=%d r=%d tag=%d o=%d max=%d\n",l,r,Seg[o].tag,o,Seg[o].maxx);

    if(l!=r){

        int mid=(l+r)>>1;

        debug(l,mid,Seg[o].lson);

        debug(mid+1,r,Seg[o].rson);

    }

}

void uni(int x,int y){

    if(find(x)!=find(y)){

        erase(1,n,root[n+1],find(x));

        erase(1,n,root[n+1],find(y));

        int t=0;

        merge(root[find(x)],root[find(y)],1,n,t);

        root[find(y)]=t;

        fa[find(x)]=find(y);

        // debug(1,n,root[find(y)]);

        add(1,n,root[n+1],find(y),Seg[root[find(y)]].maxx);

    }

}

int query(int l,int r,int o,int pos){

    if(l==r){

        return Seg[o].maxx;

    }

    pushdown(o);

    int mid=(l+r)>>1;

    if(pos<=mid)

        return query(l,mid,Seg[o].lson,pos);

    else

        return query(mid+1,r,Seg[o].rson,pos);

}

int main(){

    freopen("8.in","r",stdin);

    freopen("test.out","w",stdout);

    // scanf("%d",&n);

    n=read();

    Seg[0].maxx=-0x3f3f3f3f;

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

        fa[i]=i,root[i]=0;

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

        int midx;

        // scanf("%d",&midx);

        midx=read();

        add(1,n,root[i],i,midx);

        add(1,n,root[n+1],i,midx);

    }

    // scanf("%d",&q);

    q=read();

    char opt[4];

    for(int i=1;i<=q;i++){

        opt[0]=Getchar();

        while(opt[0]!='U'&&opt[0]!='A'&&opt[0]!='F')

            opt[0]=Getchar();

        if(opt[0]=='U'){

            int x,y;

            // scanf("%d %d",&x,&y);

            x=read();

            y=read();

            uni(x,y);

            continue;

        }

        opt[1]=Getchar();

        while(opt[1]!='1'&&opt[1]!='2'&&opt[1]!='3')

            opt[1]=Getchar();

        if(opt[0]=='A'&&opt[1]=='1'){

            int x=read(),v=read();

            // scanf("%d %d",&x,&v);

            erase(1,n,root[n+1],find(x));

            add(1,n,root[find(x)],x,v);

            add(1,n,root[n+1],find(x),Seg[root[find(x)]].maxx);

            continue;

        }

        else if(opt[0]=='A'&&opt[1]=='2'){

            int x=read(),v=read();

            // scanf("%d %d",&x,&v);

            add(1,n,root[n+1],find(x),v);

            Seg[root[find(x)]].maxx+=v;

            Seg[root[find(x)]].tag+=v;

            pushdown(root[find(x)]);

            continue;

        }

        else if(opt[0]=='A'&&opt[1]=='3'){

            int v=read();

            alladd+=v;

            continue;

        }

        else if(opt[0]=='F'&&opt[1]=='1'){

            int x=read();

            printf("%d\n",query(1,n,root[find(x)],x)+alladd);

            continue;

        }

        else if(opt[0]=='F'&&opt[1]=='2'){

            int x=read();

            printf("%d\n",Seg[root[find(x)]].maxx+alladd);

            continue;

        }

        else{

            printf("%d\n",Seg[root[n+1]].maxx+alladd);

            continue;

        }

    }

    return 0;

}