说在前面的话

不要被可怕的操作吓跑，战胜恐惧的最好办法，就是面对恐惧，加油，奥利给。但冷静分析一下，好像是道大水题。

分析

分析一下，所有操作其实有用的就是维护一下，集合最大。支持合并。其他的操作都可以开一些标记记录一下。但是合并操作的复杂度如何分析，最值又如何维护。

维护最值

一般维护最值一般考虑 和平衡树。但是只有查询最值和删除集合中一个数的操作。用平衡树就大材小用了，反而会增加常数。关于如何删除集合中一个树的操作，完全可以使用维护两个堆 ，一个添加堆，一个删除堆。那么当查询最值时，如果两个堆顶一样，便都弹出。最后直接返回第一个堆 的堆顶。这个也是一个非常常用的技巧吧，大概是个延迟删除的操作。

合并

考虑 的启发式合并。我们可以类比 的合并。我们合并两个 或者是堆时。我们是考虑将小的集合插入大的集合中的。我们来分析一下时间复杂度。考虑一个数合并的次数。一开始我们有 个大小为 的集合。经过一次合并，较小的集合的大小就多了一倍。那么一个数总共需要 次合并。那么总的合并复杂度为 由于是用 维护的，所以合并所有集合的总复杂度为 。

• 细节1：要注意，任何时候变动一个数值的大小，一定要改变当前集合和全局最大值的最值。

• 细节2：自己打的标记，在输出时一定要加上去。

  代码

  #include<bits/stdc++.h>
  using namespace std;
  #define ll long long
  #define pb(x) push_back(x)
  const int N = 610000;
  int read() {
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch=='-')f=1;ch=getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
    return f ? -x : x;    
  }
  struct Heap {
    priority_queue<int> del,add;
    void ph(int x) {add.push(x);}
    void pop(int x) {del.push(x);}
    int top() {
        while(del.size() && del.top() == add.top()) del.pop(),add.pop();
        return add.top();
    }
  }All,s[N];
  vector<int> S[N];
  int Alltag,tag[N],fa[N],a[N],n;
  int findset(int x) {return fa[x] == x ? x : fa[x] = findset(fa[x]);}
  int main() {
    n = read();
    for(int i = 1;i <= n;i++) {
        a[i] = read();
        fa[i] = i;S[i].pb(i);
        s[i].ph(a[i]);All.ph(a[i]);
    }
    int Q = read();
    while(Q--) {
        char ch[10];
        scanf("%s",ch + 1);
        if(ch[1] == 'U') {
            int x = read(),y = read();
            x = findset(x);y = findset(y);
            if(x == y) continue;
            All.pop(s[x].top() + tag[x]);
            All.pop(s[y].top() + tag[y]);
            if(S[x].size() < S[y].size()) swap(x,y);
            for(auto to : S[y]) {
                int fto = findset(to);
                fa[fto] = x;
                a[to] = a[to] + tag[y] - tag[x];
                S[x].pb(to);s[x].ph(a[to]);
            }
            All.ph(s[x].top() + tag[x]);
        }
        if(ch[1] == 'A' && ch[2] == '1') {
            int x = read(),val = read();
            int fx = findset(x);
            All.pop(s[fx].top() + tag[fx]);
            s[fx].pop(a[x]);s[fx].ph(a[x] + val);a[x] += val;
            All.ph(s[fx].top() + tag[fx]);
        }
        if(ch[1] == 'A' && ch[2] == '2') {
            int x = read(),val = read();
            int fx = findset(x);
            All.pop(s[fx].top() + tag[fx]);
            tag[fx] += val;
            All.ph(s[fx].top() + tag[fx]);
        }
        if(ch[1] == 'A' && ch[2] == '3') Alltag += read();
        if(ch[1] == 'F' && ch[2] == '1') {
            int x = read();int fx = findset(x);
            printf("%d\n",a[x] + tag[fx] + Alltag);
        }
        if(ch[1] == 'F' && ch[2] == '2') {
            int x = read();x = findset(x);
            printf("%d\n",s[x].top() + tag[x] + Alltag);
        }
        if(ch[1] == 'F' && ch[2] == '3') printf("%d\n",All.top() + Alltag);
    }
    return 0;
  }