棘手的操作

写在前面的

确实，题如其名，是一道实实在在的。在隔壁JK_Lover的指导下找到了一篇非常优秀的题解，并悟了一会儿。

思路

连边和连通性——可以通过并查集维护
点的查询和加权——用vector存储每一个连通块的点
连通块加权——打标记
合并——启发式合并，同时要更新标记
全局加——开个变量记录一下（这个操作真的拉胯，感觉一只哈士奇混入狼群）
局部以及全局的最大值——开个堆记录一下，需要支持可删除存在的元素，而且还需要支持可合并

这样就可以了呢。真的是一道呢（u1s1,这个思路相对于线段树，左偏树的写法又好理解代码量又少很多只是复杂度有一点点的高）。

代码

#include<bits/stdc++.h>
#define int long long
const int N=3e5+5,INF=0x3f3f3f3f,mod=998244353;
using namespace std;

int n,q,gtag;
int a[N],ltag[N],fa[N];
vector<int > num[N];

inline int read()
{
    register int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}

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

struct node
{
    priority_queue<int > val,del;
    void push(int x){val.push(x);}
    void pop(int x){del.push(x);}
    int top(){while(del.size()&&val.top()==del.top()) val.pop(),del.pop();return val.top();}
}gmaxx,lmaxx[N];

signed main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
        fa[i]=i;
        num[i].push_back(i);
        lmaxx[i].push(a[i]);
        gmaxx.push(a[i]);
    }
    int q=read();
    while(q--)
    {
        char opt[5];
        scanf("%s",opt);
        if(opt[0]=='U')
        {
            int x,y;
            x=read();y=read();
            x=find(x);y=find(y);
            if(x!=y)
            {
                if(num[x].size()<num[y].size())    swap(x,y);
                gmaxx.pop(lmaxx[y].top()+ltag[y]);
                gmaxx.pop(lmaxx[x].top()+ltag[x]);
                for(int i=0;i<num[y].size();i++)
                {
                    int id=num[y][i];
                    fa[id]=x;
                    a[id]=a[id]+ltag[y]-ltag[x];
                    num[x].push_back(id);
                    lmaxx[x].push(a[id]);
                }
                num[y].clear();
                gmaxx.push(lmaxx[x].top()+ltag[x]);
            }
        }

        else if(opt[0]=='A')
        {
            if(opt[1]=='1')
            {
                int x,w;
                x=read();w=read();
                gmaxx.pop(lmaxx[find(x)].top()+ltag[find(x)]);
                lmaxx[find(x)].pop(a[x]);
                lmaxx[find(x)].push(a[x]+=w);
                gmaxx.push(lmaxx[find(x)].top()+ltag[find(x)]);
            }
            else if(opt[1]=='2')
            {
                int x,w;
                x=read();w=read();
                gmaxx.pop(lmaxx[find(x)].top()+ltag[find(x)]);
                ltag[find(x)]+=w;
                gmaxx.push(lmaxx[find(x)].top()+ltag[find(x)]);
            }
            else if(opt[1]=='3')
            {
                int w=read();
                gtag+=w;
            }
        }

        else if(opt[0]=='F')
        {
            if(opt[1]=='1')
            {
                int x=read();
                printf("%lld\n",a[x]+ltag[find(x)]+gtag);
            }
            else if(opt[1]=='2')
            {
                int x=read();
                printf("%lld\n",lmaxx[find(x)].top()+ltag[find(x)]+gtag);
            }
            else if(opt[1]=='3')
            {
                printf("%lld\n",gmaxx.top()+gtag);
            }
        }
    }
    return 0;
}