golB s'CBoriN

苯宝宝比较傻只会离线的，连splay都懒得学。离线算法：先处理所有U操作，建造一棵合并树，每一时刻的每一个联通块都是合并树上的一个子树，将子树化成区间，就成了“区间加某个数&&查询区间最大”的经典线段树问题了#include <cstdio>

int f[600001],son[600001][2],name[600001],dn[600001],rang[600001],N,Q,q[300001][3],w[300001],T[1111111][2],n;
int DFS[600001][2],TIME=0;
int F(int x){return f[x]==x?x:(f[x]=F(f[x]));}
int max(int x,int y){return x>y?x:y;}
void root(int x)
{
	if (!son[x][0])
	{
		name[x]=rang[x]=++TIME,dn[TIME]=x;
		return;
	}
	DFS[1][0]=x,DFS[1][1]=(son[x][0]?0:2);
	int D=1,np;
	while (D)
		switch (DFS[D][1])
		{
			case 0:
			case 1:
				np=son[DFS[D][0]][DFS[D][1]];
				DFS[D][1]++;
				DFS[D+1][0]=np;
				DFS[D+1][1]=(son[np][0]?0:2);
				if (!son[np][0])
					name[np]=rang[np]=++TIME,dn[TIME]=np;
				D++;
				break;
			case 2:
				if (son[DFS[D][0]][0])
					name[DFS[D][0]]=name[son[DFS[D][0]][0]],rang[DFS[D][0]]=rang[son[DFS[D][0]][1]];
				D--;
		}
}
void init()
{
	scanf("%d",&N);
	for (int i=1;i<=N;i++)
		scanf("%d",&w[i]);
	scanf("%d",&Q);
	for (int i=1;i<=Q;i++)
	{
		char c=getchar();
		while (c!='U'&&c!='A'&&c!='F')
			c=getchar();
		if (c=='U')
			q[i][0]=0,scanf("%d%d",&q[i][1],&q[i][2]);
		else
		{
			q[i][0]=(c=='A')?0:3;
			c=getchar();
			q[i][0]+=c-48;
			if (q[i][0]<=2)
				scanf("%d%d",&q[i][1],&q[i][2]);
			else
				if (q[i][0]<=5)
					scanf("%d",&q[i][1]);
		}
	}
	for (int i=1;i<=N;i++)
		f[i]=i;
	n=N;
	for (int i=1;i<=Q;i++)
		if (!q[i][0])
		{
			int f1=F(q[i][1]),f2=F(q[i][2]);
			if (f1!=f2)
			{
				n++;
				f[f1]=f[f2]=f[n]=n;
				son[n][0]=f1,son[n][1]=f2;
			}
		}
	for (int i=1;i<=n;i++)
		if (f[i]==i)
			root(i);
}
void bt(int p,int l,int r)
{
	if (l==r)
		T[p][0]=w[dn[l]],T[p][1]=0;
	else
	{
		int m=l+r>>1;
		bt(p<<1,l,m),bt((p<<1)|1,m+1,r);
		T[p][0]=max(T[p<<1][0],T[(p<<1)|1][0]);
	}
}
int P(int p,int l,int r,int L,int R,int d)
{
	if (l==L&&r==R)
	{
		T[p][0]+=d,T[p][1]+=d;
		return T[p][0];
	}
	else
	{
		int m=l+r>>1;
		if (R<=m)
			return T[p][0]=max(P(p<<1,l,m,L,R,d),T[(p<<1)|1][0])+T[p][1];
		else
			if (L>m)
				return T[p][0]=max(T[p<<1][0],P((p<<1)|1,m+1,r,L,R,d))+T[p][1];
			else
				return T[p][0]=max(P(p<<1,l,m,L,m,d),P((p<<1)|1,m+1,r,m+1,R,d))+T[p][1];
	}
}
int G(int p,int l,int r,int L,int R)
{
	if (l==L&&r==R)
		return T[p][0];
	else
	{
		int m=l+r>>1;
		if (R<=m)
			return G(p<<1,l,m,L,R)+T[p][1];
		else
			if (L>m)
				return G((p<<1)|1,m+1,r,L,R)+T[p][1];
			else
				return max(G(p<<1,l,m,L,m),G((p<<1)|1,m+1,r,m+1,R))+T[p][1];
	}
}
int main()
{
	init();
	n=N;
	for (int i=1;i<=N;i++)
		f[i]=i;
	int f0,f1;
	bt(1,1,N);
	for (int i=1;i<=Q;i++)
		switch (q[i][0])
		{
			case 0:
				f0=F(q[i][1]),f1=F(q[i][2]);
				if (f0!=f1)
				{
					n++;
					f[f0]=f[f1]=f[n]=n;
				}
				break;
			case 1:P(1,1,N,name[q[i][1]],name[q[i][1]],q[i][2]);break;
			case 2:P(1,1,N,name[F(q[i][1])],rang[F(q[i][1])],q[i][2]);break;
			case 3:P(1,1,N,1,N,q[i][1]);break;
			case 4:printf("%d\n",G(1,1,N,name[q[i][1]],name[q[i][1]]));break;
			case 5:printf("%d\n",G(1,1,N,name[F(q[i][1])],rang[F(q[i][1])]));break;
			case 6:printf("%d\n",G(1,1,N,1,N));break;
		}
	return 0;
}