题面
https://www.luogu.com.cn/problem/P3273
大意是给n个初始独立的点，有7种操作：
1、在两个点之间连一条无向边
2、给一个点加上一个权值
3、给一个点所在的连通块中的所有点加上一个权值
4、给所有点加上一个权值
5、查询一个点的权值
6、查询一个点所在的连通块中的所有点的最大权值
7、查询所有点的最大权值
分析
查询和修改操作都很像线段树，但是由于连边操作，序号是断裂的
考虑离线用链表来维护点的线段树序号，当连接两个连通块时，将两个连通块的序号序列用链表相连，最后按照链表上的顺序给点编号
并查集维护连通块，这样重标号的序列每次合并后都是一个连续的区间了
再将所有操作做一遍，连边操作就将区间端点扩张一下即可，剩下就是线段树基操了
代码
#include <iostream> #include <cstdio> #include <cstring> #define lson (x<<1) #define rson ((x<<1)+1) using namespace std; const int Inf=2147483647; const int N=3e5+10; struct Task { int tp,x,y; }p[N]; int n,m; int f[N],t[4*N],lz[4*N],ref[N],bac[N],cnt,l[N],r[N],pre[N],nex[N],st[N],ed[N],a[N]; int Get_F(int x) {return f[x]==x?x:f[x]=Get_F(f[x]);} void Pushdown(int x,int l,int r) { if (!lz[x]) return; int mid=l+r>>1; t[lson]+=lz[x];lz[lson]+=lz[x]; t[rson]+=lz[x];lz[rson]+=lz[x]; lz[x]=0; } void Change(int x,int l,int r,int ll,int rr,int k) { if (ll<=l&&r<=rr) {t[x]+=k;lz[x]+=k;return;} int mid=l+r>>1; Pushdown(x,l,r); if (ll<=mid) Change(lson,l,mid,ll,rr,k); if (mid<rr) Change(rson,mid+1,r,ll,rr,k); t[x]=max(t[lson],t[rson]); } int Query(int x,int l,int r,int ll,int rr) { if (ll<=l&&r<=rr) return t[x]; int mid=l+r>>1,ans=-Inf; Pushdown(x,l,r); if (ll<=mid) ans=Query(lson,l,mid,ll,rr); if (mid<rr) ans=max(ans,Query(rson,mid+1,r,ll,rr)); return ans; } int main() { scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&a[i]),f[i]=st[i]=ed[i]=i; scanf("%d",&m); for (int i=1,x,y;i<=m;i++) { char s[4]; scanf("%s",s); if (s[0]=='U') { scanf("%d%d",&x,&y); x=Get_F(x);y=Get_F(y); if (x!=y) f[y]=x,pre[st[y]]=ed[x],nex[ed[x]]=st[y],ed[x]=ed[y]; p[i]=(Task){0,x,y}; } if (s[0]=='A') { scanf("%d",&x); if (s[1]<'3') scanf("%d",&y); p[i]=(Task){s[1]-'0',x,y}; } if (s[0]=='F') { if (s[1]<'3') scanf("%d",&x); p[i]=(Task){s[1]-'0'+3,x,y}; } } for (int i=1;i<=n;f[i]=i,i++) if (!pre[i]) for (int j=i;j;j=nex[j]) bac[l[j]=r[j]=ref[j]=++cnt]=j,Change(1,1,n,ref[j],ref[j],a[j]); for (int i=1,x,y;i<=m;i++) { x=p[i].x;y=p[i].y; if (!p[i].tp) { x=Get_F(x);y=Get_F(y); if (x!=y) f[y]=x,l[x]=min(l[x],l[y]),r[x]=max(r[x],r[y]); } if (p[i].tp==1) Change(1,1,n,ref[x],ref[x],y); if (p[i].tp==2) x=Get_F(x),Change(1,1,n,l[x],r[x],y); if (p[i].tp==3) Change(1,1,n,1,n,x); if (p[i].tp==4) printf("%d ",Query(1,1,n,ref[x],ref[x])); if (p[i].tp==5) x=Get_F(x),printf("%d ",Query(1,1,n,l[x],r[x])); if (p[i].tp==6) printf("%d ",t[1]); } }