题目概述

加边；单点加；连通块加；整体加；单点询问；连通块最大值；整体最大值。

解题报告

平衡树启合好像会TLE来着，加边只求最大值就是个可并堆嘛……连通块加打tag，整体加记个量，但是要单点加怎么办啊？左偏树不保证树高所以凉凉，配对堆不会写啊。随机堆大法好！

随机堆合并的时候随机左右合并，修改点的时候和二叉堆一样往上和往下看看能不能交换，注意各种儿子父亲之间的关系还有标记下传。

示例程序

200题祭（祭个蛇皮，我怎么现在才到200题啊）。

#include<cstdio>
#include<cstdlib>
#include<set>
using namespace std;
const int maxn=300000;

int RD[1000000],n,te,a[maxn+5],ro[maxn+5],son[maxn+5][2],fa[maxn+5],tag[maxn+5];
int fat[maxn+5],all,MAX;multiset<int> S;

inline int Rand() {static int pos=0;return RD[pos+1<1e6?pos++:pos=0];}
int getfa(int x) {return x==fat[x]?x:fat[x]=getfa(fat[x]);}
inline void Addtag(int p,int k) {if (!p) return;a[p]+=k;tag[p]+=k;}
inline void Pushdown(int p) {if (tag[p]) Addtag(son[p][0],tag[p]),Addtag(son[p][1],tag[p]),tag[p]=0;}
int Merge(int A,int B){
    if (!A||!B) return A+B;if (a[A]<a[B]) swap(A,B);Pushdown(A);int d=Rand();son[A][d]=Merge(son[A][d],B);
    if (son[A][0]) fa[son[A][0]]=A;if (son[A][1]) fa[son[A][1]]=A;return A;
}
#define Son(x) ((x)==son[fa[x]][1])
inline void Swap(int x,int f){
    int d=Son(x);swap(son[x],son[f]);son[x][d]=f;if (son[f][0]) fa[son[f][0]]=f;if (son[f][1]) fa[son[f][1]]=f;
    if (son[x][d^1]) fa[son[x][d^1]]=x;if (fa[f]) son[fa[f]][Son(f)]=x; else ro[getfa(x)]=x;fa[x]=fa[f];fa[f]=x;
}
inline void Add(int x,int v){
    static int top=0,stk[maxn+5];for (int i=x;i;i=fa[i]) stk[++top]=i;while (top) Pushdown(stk[top--]);a[x]+=v;
    for (int f=fa[x];f&&a[x]>a[f];f=fa[x]) Swap(x,f);
    for (int l=son[x][0],r=son[x][1];l&&a[x]<a[l]||r&&a[x]<a[r];l=son[x][0],r=son[x][1])
        {if (!l||r&&a[r]>a[l]) l=r;Pushdown(l);Swap(l,x);}
}
#define Insert(x) (S.insert(-a[ro[x]]),MAX=-(*S.begin()))
#define Delete(x) (S.erase(S.lower_bound(-a[ro[x]])))
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    srand(759405);for (int i=0;i<1000000;i++) RD[i]=rand()&1;
    scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d",&a[i]),ro[i]=fat[i]=i,Insert(i);
    for (scanf("%d",&te);te;te--){
        char ch=getchar();while (ch!='A'&&ch!='F'&&ch!='U') ch=getchar();int tp,x,y;
        if (ch=='U'){
            scanf("%d%d",&x,&y);x=getfa(x);y=getfa(y);if (x==y) continue;
            Delete(x);Delete(y);ro[x]=Merge(ro[x],ro[y]);Insert(x);fat[y]=x;
        } else if (ch=='A'){
            if ((scanf("%d%d",&tp,&x),tp)==1) scanf("%d",&y),Delete(getfa(x)),Add(x,y),Insert(getfa(x));
            else if (tp==2) scanf("%d",&y),Delete(getfa(x)),Addtag(ro[getfa(x)],y),Insert(getfa(x)); else all+=x;
        } else{
            if ((scanf("%d",&tp),tp)==1) scanf("%d",&x),Add(x,0),printf("%d\n",a[x]+all);
            else if (tp==2) scanf("%d",&x),printf("%d\n",a[ro[getfa(x)]]+all); else printf("%d\n",MAX+all);
        }
    }return 0;
}