长得一点也不像线段树的线段树思维题。。。
看到连边首先想到了$LCT$。但是。。。$LCT$不能对一群不在同一条链上的节点修改和查询。
换个思路想：如果同一联通块节点编号连续的话，是不是就好维护了呢？这样问题就变成了保证每次连边后形成的联通块编号连续，然后就可以并查集$+$线段树维护了。
题目没有强制在线，自然可以把操作离线下来。
一开始每个点都是联通块，拥有一个编号序列（这里编号序列是一个相对位置，两个不同的联通块编号靠前靠后不会互相影响的）。当连接两个联通块时，把它们两个的编号序列拼接起来。蒟蒻用的朴素的链表，可以$O(1)$地将两个块编号序列连接起来。
然后用并查集维护联通块大小，线段树区间加维护最大值就好了$QwQ$。
注意！数据有不合法连边，要特判。
具体实现还是看代码清晰一些：（蒟蒻没写过链表，自己$yy$用数组写的的可能比较丑陋。。。）
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define maxn 300005
#define inf 0x3f3f3f3f
using namespace std;
inline int read(){
int x=0,y=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return y?-x:x;
}
template<typename T>
inline T read(){
T x=0;
int y=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return y?-x:x;
}
int nex[maxn],tail[maxn],a[maxn],pos[maxn],seg[maxn],fa[maxn],siz[maxn],cnt,n;
//nex指向链表节点的下一项，tail是链表尾指针
//seg是重新编的号，pos是每个seg对应的实际位置
//fa是并查集
int find(int x){
if(fa[x]==x)return x;
return fa[x]=find(fa[x]);
}
struct Order{
int s,x,d;//s是操作类型
}o[maxn];//存储操作
struct Segment_Tree{
int ma[maxn<<2],tag[maxn<<2];
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
inline void update(int node){
ma[node]=max(ma[ls(node)],ma[rs(node)]);
}
inline void datadown(int node,int d){
ma[node]+=d,tag[node]+=d;
}
inline void pushdown(int node){
datadown(ls(node),tag[node]);
datadown(rs(node),tag[node]);
tag[node]=0;
}
void build(int l=1,int r=cnt,int node=1){
if(l==r){
ma[node]=a[pos[l]];
fa[l]=l,siz[l]=1;
//重置并查集和siz
return;
}
int mid=l+r>>1;
build(l,mid,ls(node));
build(mid+1,r,rs(node));
update(node);
}
void add(int L,int R,int l,int r,int node,int d){
if(L<=l&&R>=r){
datadown(node,d);
return;
}
if(tag[node])pushdown(node);
int mid=l+r>>1;
if(L<=mid)add(L,R,l,mid,ls(node),d);
if(R>mid)add(L,R,mid+1,r,rs(node),d);
update(node);
}
int ask(int L,int R,int l,int r,int node){
if(L<=l&&R>=r)return ma[node];
if(tag[node])pushdown(node);
int mid=l+r>>1,ans=-inf;
if(L<=mid)ans=ask(L,R,l,mid,ls(node));
if(R>mid)ans=max(ans,ask(L,R,mid+1,r,rs(node)));
return ans;
}
}st;//线段树常规操作
int main(){
n=read();
for(register int i=1;i<=n;++i)
a[i]=read(),tail[i]=fa[i]=i;
int m=read();
for(register int i=1;i<=m;++i){
char s[5];
scanf("%s",s);
if(s[0]=='A'){
o[i].s=-s[1]+'0';
if(s[1]<'3')o[i].x=read();
o[i].d=read();
}
else if(s[0]=='F'){
o[i].s=s[1]-'0';
if(s[1]<'3')o[i].x=read();
}
else {
o[i].s=45562;
int x=read(),y=read(),u=find(x),v=find(y);
o[i].x=x,o[i].d=y;
if(u==v)continue;//特判
nex[tail[u]]=v,tail[u]=tail[v],fa[v]=u;
//把两段链表连起来
}
}
//s<0为A操作，|s|为其后跟的编号
//s==45562连边操作
//s>0为F操作，s为其后跟的编号
for(register int i=1;i<=n;++i)
if(fa[i]==i){
//如果一个点在并查集里是根的话，它也是所在链表的头
for(register int j=i;j;j=nex[j])seg[j]=++cnt,pos[cnt]=j;
//遍历每一个链表，直接按链表顺序编号
}
st.build();//初始建树
for(register int i=1;i<=m;++i){
int s=o[i].s;
if(s==45562){
int u=find(o[i].x),v=find(o[i].d);
if(u==v)continue;
siz[u]+=siz[v],fa[v]=u;
//维护一下siz便于获取联通块的区间
}
else if(s<0){
if(s==-1)st.add(seg[o[i].x],seg[o[i].x],1,cnt,1,o[i].d);
else if(s==-2){
int u=find(o[i].x);
st.add(seg[u],seg[u]+siz[u]-1,1,cnt,1,o[i].d);
//并查集根的编号+siz-1就是该联通块当前所代表的区间
}
else st.add(1,cnt,1,cnt,1,o[i].d);
}
else {
if(s==1)printf("%d\n",st.ask(seg[o[i].x],seg[o[i].x],1,cnt,1));
else if(s==2){
int u=find(o[i].x);
printf("%d\n",st.ask(seg[u],seg[u]+siz[u]-1,1,cnt,1));
}
else printf("%d\n",st.ma[1]);
}
}
}
