C++(clang++11) 解法, 执行用时: 456ms, 内存消耗: 76216K, 提交时间: 2020-11-04 16:02:59

/*
U  x y:合并他们的两个堆

A1 x v:先pop到del,再push回val

A2 x v:连通块的变量处理

A3 x v:全局变量处理

F1 x:找到所属连通块,加上局部和全局变量

F2 x:直接pop

F3 x:整体的pop
*/
#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int N=3e5+10;

int n,zt,m;
ll a[N],jub[N];int f[N];

vector<int>num[N];
//连通块里的点
struct nkl
{
	priority_queue<ll>q,del;

	void push(ll x){q.push(x);}
	void pop(ll x){del.push(x);}
	int top()
	{
		while(del.size()&&del.top()==q.top())
			del.pop(),q.pop();
		return q.top();
	}
}wl,bl[N];

inline int find(int x)
{
	if(x==f[x]) return x;
	return f[x]=find(f[x]);
}

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		f[i]=i;//并查集初始化
		num[i].push_back(i);//连通块的点
		wl.push(a[i]);
		bl[i].push(a[i]);
		//全局与局部的点 
	}

	scanf("%d",&m);char ins[5];int x,v;
	while(m--)
	{
		scanf("%s",ins);
		if(ins[0]=='U')
		{
			scanf("%d%d",&x,&v);
			x=find(x),v=find(v);
			if(x==v) continue;

			if(num[x].size()<num[v].size()) swap(x,v);
			wl.pop(bl[v].top()+jub[v]);
			wl.pop(bl[x].top()+jub[x]);
			int len=num[v].size();
			for (int i=0;i<len;i++)
			{
				int j=num[v][i];
				f[j]=x;
				a[j]=a[j]+jub[v]-jub[x];
				bl[x].push(a[j]);
				num[x].push_back(j);
			}//开始合并
			num[v].clear();
			wl.push(bl[x].top()+jub[x]);
			//重回最大值
		}
		else if(ins[0]=='A')
		{
			if(ins[1]=='1')
			{
				scanf("%d%d",&x,&v);
				int u=find(x);
				wl.pop(bl[u].top()+jub[u]);
				bl[u].pop(a[x]);
				a[x]+=v;
				bl[u].push(a[x]);
				wl.push(bl[u].top()+jub[u]);
			}
			else if(ins[1]=='2')
			{
				scanf("%d%d",&x,&v);int u=find(x);
				wl.pop(bl[u].top()+jub[u]);
				jub[u]+=v;
				wl.push(bl[u].top()+jub[u]);
			}
			else scanf("%d",&v),zt+=v;
		}
		else
		{
			if(ins[1]=='3')
				printf("%lld\n",wl.top()+(ll)zt);
			else
			{
				scanf("%d",&x);
				int u=find(x);
				if(ins[1]=='1')
					printf("%lld\n",(ll)a[x]+zt+jub[u]);
				else
					printf("%lld\n",(ll)bl[u].top()+zt+jub[u]);
			}
		}
	}
	
	return 0;
}