测试地址：棘手的操作
做法：本题需要用到线段树+并查集+离线处理。
话说这题号还真喜庆……又据说这题原来是毒瘤数据结构，什么堆套左偏树之类……但是本蒟蒻从某大佬那里得到了离线做法的启示，所以就水了一发。
我们尝试构造一种点的排列方案，使得操作中涉及的所有连通块在排列中都是一个连续区间。这可以构造出来吗？当然可以！首先我们把每个点都看作一个区间，每当合并两个连通块，就是将两个区间放在一起，这个我们可以用链表维护。最后我们再把所有分散的连通块连起来，得到的链表上的点的顺序就是我们要求的排列了。
然后就是线段树区间修改区间询问的裸题了，同时用并查集维护一下当前的连通情况即可，时间复杂度是。
以下是本人代码：
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll inf=1000000000;
int n,m,first,nxt[300010],fa[300010],head[300010],tail[300010];
int pos[300010],q[300010];
ll a[300010],mx[1200010],p[1200010]={0},opx[300010],opy[300010];
char op[300010][4];
int find(int x)
{
int r=x,i=x,j;
while (r!=fa[r]) r=fa[r];
while (i!=r)
{
j=fa[i];
fa[i]=r;
i=j;
}
return r;
}
void merge(int x,int y)
{
int fx=find(x),fy=find(y);
fa[fy]=fx;
tail[fx]=tail[fy];
}
void pushdown(int no)
{
if (p[no]!=0)
{
mx[no<<1]+=p[no],mx[no<<1|1]+=p[no];
p[no<<1]+=p[no],p[no<<1|1]+=p[no];
p[no]=0;
}
}
void pushup(int no)
{
mx[no]=max(mx[no<<1],mx[no<<1|1]);
}
void buildtree(int no,int l,int r)
{
if (l==r)
{
mx[no]=a[q[l]];
return;
}
int mid=(l+r)>>1;
buildtree(no<<1,l,mid);
buildtree(no<<1|1,mid+1,r);
pushup(no);
}
void modify(int no,int l,int r,int s,int t,ll c)
{
if (l>=s&&r<=t)
{
mx[no]+=c;
p[no]+=c;
return;
}
pushdown(no);
int mid=(l+r)>>1;
if (s<=mid) modify(no<<1,l,mid,s,t,c);
if (t>mid) modify(no<<1|1,mid+1,r,s,t,c);
pushup(no);
}
ll query(int no,int l,int r,int s,int t)
{
if (l>=s&&r<=t) return mx[no];
pushdown(no);
int mid=(l+r)>>1;
ll mxx=-inf*inf;
if (s<=mid) mxx=max(mxx,query(no<<1,l,mid,s,t));
if (t>mid) mxx=max(mxx,query(no<<1|1,mid+1,r,s,t));
return mxx;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%s",op[i]);
if (op[i][0]=='U'||(op[i][0]=='A'&&op[i][1]<='2'))
scanf("%lld%lld",&opx[i],&opy[i]);
else if (op[i][0]=='A'||(op[i][0]=='F'&&op[i][1]<='2'))
scanf("%lld",&opx[i]);
}
for(int i=1;i<=n;i++)
fa[i]=tail[i]=i;
for(int i=1;i<=m;i++)
if (op[i][0]=='U'&&find(opx[i])!=find(opy[i]))
{
nxt[tail[find(opx[i])]]=find(opy[i]);
merge(opx[i],opy[i]);
}
first=n+1;
for(int i=1;i<n;i++)
if (find(i)!=find(i+1))
{
nxt[tail[find(i)]]=find(i+1);
first=min(first,find(i));
merge(i,i+1);
}
if (first==n+1) first=find(1);
for(int i=1,now=first;i<=n;i++,now=nxt[now])
{
pos[now]=i;
q[i]=now;
}
buildtree(1,1,n);
for(int i=1;i<=n;i++)
fa[i]=i,tail[i]=pos[i];
for(int i=1;i<=m;i++)
{
if (op[i][0]=='U'&&find(opx[i])!=find(opy[i]))
merge(opx[i],opy[i]);
if (op[i][0]=='A')
{
if (op[i][1]=='1') modify(1,1,n,pos[opx[i]],pos[opx[i]],opy[i]);
if (op[i][1]=='2') modify(1,1,n,pos[find(opx[i])],tail[find(opx[i])],opy[i]);
if (op[i][1]=='3') modify(1,1,n,1,n,opx[i]);
}
if (op[i][0]=='F')
{
ll ans;
if (op[i][1]=='1') ans=query(1,1,n,pos[opx[i]],pos[opx[i]]);
if (op[i][1]=='2') ans=query(1,1,n,pos[find(opx[i])],tail[find(opx[i])]);
if (op[i][1]=='3') ans=query(1,1,n,1,n);
printf("%lld
",ans);
}
}
return 0;
}