每日一题 [SCOI2011]棘手的操作 题解

一道不错的有关于各种tag我们熟练维护的题
首先这题可以1个log的左偏树做，但是考虑到细节较多我们用两个log的启发式合并来写，当然你也可以用splay可以自适应做到1个log。
我们这里的splay换为set方便维护
首先我们单点加和整体加都可以非常方便的维护，于是我们只剩下对于一个联通的集合加一个数，
这是一个经典的套路我们对于这个集合维护一个tag，然后我们两个合并的时候用一个tag减去另一个的tag，然后更新它新的权值，相当于这么一个tag的dat，然后update以后我们就可以用启发式合并！
剩下就是一个细节的问题，我们只需要用并查集维护连通性，每次从儿子像父亲连边，同时合并就可以了，也就是并查集的过程中哪个部分size大我们就钦定往它上连边！
维护全局最大是还需要一个全局set，大概就可以了，注意我们这里的set是有重复的，即都需要使用multiset！
代码：

#include<bits/stdc++.h>
#define fgx cerr<<"-----------------------"<<endl
#define LL long long
#define DB double
#define pb push_back
#define mp make_pair
using namespace std;
namespace IO{
    const int BS=(1<<23)+5; int Top=0;
    char Buffer[BS],OT[BS],*OS=OT,*HD,*TL,SS[20]; const char *fin=OT+BS-1;
    char Getchar(){if(HD==TL){TL=(HD=Buffer)+fread(Buffer,1,BS,stdin);} return (HD==TL)?EOF:*HD++;}
    void flush(){fwrite(OT,1,OS-OT,stdout),OS=OT;}
    void Putchar(char c){*OS++ =c;if(OS==fin)flush();}
    void write(LL x){
        if(!x){Putchar('0'),Putchar('\n'); return;} if(x<0) x=-x,Putchar('-');
        while(x) SS[++Top]=x%10,x/=10;
        while(Top) Putchar(SS[Top]+'0'),--Top; Putchar('\n');
    }
    inline LL read(){
        LL nm=0; bool fh=true; char cw=getchar();
        for(;!isdigit(cw);cw=getchar()) fh^=(cw=='-');
        for(;isdigit(cw);cw=getchar()) nm=nm*10+(cw-'0');
        return fh?nm:-nm;
    }
} using namespace IO;
#define M 300020
#define vl first
#define ps second
#define IT multiset<LL>::iterator
#define ITP multiset<pair<LL,int> >::iterator
int n,m,fa[M]; LL val[M],tg[M],alltg;
multiset<pair<LL,int> >s[M]; multiset<LL>S;
inline LL gtmx(int f){ITP it=s[f].end();it--; return (LL)(*it).vl+tg[f];}
inline void ins(LL x){S.insert(x);}
inline void del(LL x){IT it=S.lower_bound(x); S.erase(it);}
inline int find(int x){return (fa[x]==x)?x:(fa[x]=find(fa[x]));}
int main(){
    n=read();
    for(int i=1;i<=n;i++) val[i]=read(),s[i].insert(mp(val[i],i)),fa[i]=i,ins(gtmx(i));
    m=read();
    for(int i=1;i<=m;i++){
        char ch[15]; scanf("%s",ch);
        if(ch[0]=='U'){
            int x=read(),y=read(),fx=find(x),fy=find(y); if(fx==fy) continue;
            if(s[fx].size()>s[fy].size()) swap(fx,fy); del(gtmx(fx)),del(gtmx(fy));
            for(ITP it=s[fx].begin();it!=s[fx].end();it++){int nd=(*it).ps; val[nd]+=tg[fx]-tg[fy],s[fy].insert(mp(val[nd],nd));}
            s[fx].clear(),tg[fx]=0,fa[fx]=fy,ins(gtmx(fy));
        } else if(ch[0]=='A'&&ch[1]=='1'){
            int x=read(),y=read(),fx=find(x); del(gtmx(fx));
            ITP it=s[fx].lower_bound(mp(val[x],x)); s[fx].erase(it);
            val[x]+=(LL)y,s[fx].insert(mp(val[x],x)),ins(gtmx(fx));
        } else if(ch[0]=='A'&&ch[1]=='2'){
            int x=read(),y=read(),fx=find(x);
            del(gtmx(fx)),tg[fx]+=(LL)y,ins(gtmx(fx));
        } else if(ch[0]=='A'&&ch[1]=='3'){
            int y=read(); alltg+=(LL)y;
        } else if(ch[0]=='F'&&ch[1]=='1'){
            int x=read(),fx=find(x);
            write(val[x]+tg[fx]+alltg);
        } else if(ch[0]=='F'&&ch[1]=='2'){
            int x=read(),fx=find(x); ITP it=s[fx].end();it--;
            write((LL)(*it).vl+tg[fx]+alltg);
        } else{
            IT it=S.end();it--; write((LL)(*it)+alltg);
        }
    } flush();
    return 0;
}