现场写了一个 multiset 加启发式合并的东西，但是常数过大，想问问有没有什么可以卡过去的方法……/kel 因为感觉 multiset 的常数不至于到卡不过去的地步/kk

#include <bits/stdc++.h>
using namespace std;
typedef double db;
//#define int long long
#define fi first
#define se second
#define mk make_pair
#define pb emplace_back
#define poly vector<int>
#define Bt(a) bitset<a>
#define bc __builtin_popcount
#define pc putchar
#define ci const int&
const int mod = 998244353;
const db eps = 1e-10;
inline int Max(ci x, ci y) {return x > y ? x : y;}
inline int Min(ci x, ci y) {return x < y ? x : y;}
inline db Max(db x, db y) {return x - y > eps ? x : y;}
inline db Min(db x, db y) {return x - y < eps ? x : y;}
inline int Add(ci x, ci y, ci M = mod) {return (x + y) % M;}
inline int Mul(ci x, ci y, ci M = mod) {return 1ll * x * y % M;}
inline int Dec(ci x, ci y, ci M = mod) {return (x - y + M) % M;}
typedef pair<int, int> pii;
inline int Abs(int x) {return x < 0 ? -x : x;}
//char buf[1<<21],*p1=buf,*p2=buf;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char Obuf[105000],*O=Obuf;//Siz shoule be the size of Out File
int pst[30],ptop;
inline void Fprint(){fwrite(Obuf,1,O-Obuf,stdout);}
inline void Fwrite(int x){
  if(x==0){*O++='0';if(O-Obuf>100000)Fprint(),O=Obuf;return;}
  if(x<0)*O++='-',x=-x;ptop=0;
  while(x)pst[++ptop]=x%10,x/=10;
  while(ptop)*O++=pst[ptop--]+'0';
  if(O-Obuf>100000)Fprint(),O=Obuf;
}
inline int read() {
    int s = 0, w = 1;
    char ch = getchar();
    while (!isdigit(ch)) {if (ch == '-') w = -1;ch = getchar();}
    while (isdigit(ch)) {s = s * 10 + ch - '0';ch = getchar();}
    return s * w;
}
inline void write(int x) {
    if (x < 0)putchar('-'), x = -x;
    if (x > 9)write(x / 10);
	pc(x % 10 + '0');
}
inline int qpow(int x, int y) {
    int res = 1;
    while (y) {if (y & 1)res = Mul(res, x);x = Mul(x, x);y >>= 1;}
    return res;
}
inline void cadd(int &x, int y) {x += y;}
inline void cmul(int &x, int y) {x *= y;}
inline void cmax(int &x, int y) {x = Max(x, y);}
inline void cmin(int &x, int y) {x = Min(x, y);}
const int N = 3e5 + 10;
const int inf = 1 << 30;
namespace Refined_heart{
	#define IT multiset<int>::iterator 
	int f[N],mv[N],All,siz[N],n,a[N],q,tag[N];
	inline int find(int x){
		if(x==f[x])return x;
		return f[x]=find(f[x]);
	}
	multiset<int>S[N],Al;
	poly A[N];
	void merge(int u,int v){
		int fu=find(u);
		int fv=find(v);
		if(fu==fv)return;
		if(siz[fu]>siz[fv]){
			swap(u,v);
			swap(fu,fv);
		}
		IT it=Al.find(mv[fu]+tag[fu]);
		Al.erase(it);
		it=Al.find(mv[fv]+tag[fv]);
		Al.erase(it);
		for(auto v:A[fu]){
			a[v]+=tag[fu];
			a[v]-=tag[fv];
			S[fv].insert(a[v]);
			f[v]=fv;
			A[fv].pb(v);
			cmax(mv[fv],a[v]);
		}
		Al.insert(mv[fv]+tag[fv]);
		siz[fv]+=siz[fu];
	}
	char ss[10];
	void solve(){
		n=read();
		for(int i=1;i<=n;++i)a[i]=read(),f[i]=i,mv[i]=a[i],siz[i]=1,A[i].pb(i);
		for(int i=1;i<=n;++i)Al.insert(a[i]),S[i].insert(a[i]);
		q=read();
		int x=0,v=0,fx=0,u=0;
		while(q--){
			cin>>ss;
			if(ss[0]=='U'){
				u=read(),v=read();
				merge(u,v);
				continue;
			}
			if(ss[0]=='A'){
				if(ss[1]=='1'){
					x=read(),v=read();
					fx=find(x);
					IT it=S[fx].find(a[x]);
					S[fx].erase(it);
					a[x]+=v;
					S[fx].insert(a[x]);
					it=Al.find(mv[fx]+tag[fx]);
					Al.erase(it);
					mv[fx]=(*S[fx].rbegin());
					Al.insert(mv[fx]+tag[fx]);
					continue;
				}
				if(ss[1]=='2'){
					x=read(),v=read();
					fx=find(x);
					IT it=Al.find(mv[fx]+tag[fx]);
					Al.erase(it);
					tag[fx]+=v;
					Al.insert(mv[fx]+tag[fx]);
					continue;
				}
				if(ss[1]=='3'){v=read();All+=v;}
			}
			if(ss[0]=='F'){
				if(ss[1]=='1'){
					x=read();
					fx=find(x);
					write((a[x]+All+tag[fx]));
					pc('\n');
					continue;
				}
				if(ss[1]=='2'){
					x=read();
					fx=find(x);
					write((mv[fx]+tag[fx]+All));
					pc('\n');
					continue;
				}
				if(ss[1]=='3'){
					write((*Al.rbegin())+All);
					pc('\n');
				}
			}
		}
	}
}
signed main(){
	freopen("in.txt","r",stdin);
//	freopen("d.in","r",stdin);
	freopen("d.out","w",stdout);
 	
	Refined_heart::solve();
	return 0;
}
/*
3
0 0 0
8
A1 3 -20
A1 2 20
U 1 3
A2 1 10
F1 3
F2 3
A3 -10
F3

*/