题目描述：
题解：
离线线段树+dfs序。
如果$v$都$geq 0$的话就好做多了。但是涉及到负数的话就需要多记录信息。
考虑离线先建出所给森林。（在同一连通块上连边没有改变连通性）
然后把dfs序搞出来就可以区间加法区间求最大了。
代码：
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N = 300050; const int inf = 0x3f3f3f3f; template<typename T> inline void read(T&x) { T f = 1,c = 0;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();} x = f*c; } int n,m,tot,ff[N<<1],hed[N<<1],cnt,w[N]; int findff(int u){return u==ff[u]?u:ff[u]=findff(ff[u]);} char op[10]; struct atn { int op,x,v; }p[N]; struct EG { int to,nxt; }e[N<<1]; void ae(int f,int t) { e[++cnt].to = t; e[cnt].nxt = hed[f]; hed[f] = cnt; } int tin[N<<1],tout[N<<1],tim,pla[N<<1]; void dfs(int u) { tin[u]=++tim,pla[tim]=u; for(int j=hed[u];j;j=e[j].nxt) dfs(e[j].to); tout[u] = tim; } struct segtree { int v[N<<3],tag[N<<3]; void add(int u,int d) { v[u]+=d,tag[u]+=d; } void pushdown(int u) { if(tag[u]) { add(u<<1,tag[u]); add(u<<1|1,tag[u]); tag[u] = 0; } } void update(int u){v[u]=max(v[u<<1],v[u<<1|1]);} void build(int l,int r,int u) { if(l==r) { if(pla[l]<=n)v[u] = w[pla[l]]; else v[u] = -inf; return ; } int mid = (l+r)>>1; build(l,mid,u<<1); build(mid+1,r,u<<1|1); update(u); } void insert(int l,int r,int u,int ql,int qr,int d) { if(l==ql&&r==qr) { add(u,d); return ; } pushdown(u); int mid = (l+r)>>1; if(qr<=mid)insert(l,mid,u<<1,ql,qr,d); else if(ql>mid)insert(mid+1,r,u<<1|1,ql,qr,d); else insert(l,mid,u<<1,ql,mid,d),insert(mid+1,r,u<<1|1,mid+1,qr,d); update(u); } int query(int l,int r,int u,int ql,int qr) { if(l==ql&&r==qr)return v[u]; pushdown(u); int mid = (l+r)>>1; if(qr<=mid)return query(l,mid,u<<1,ql,qr); else if(ql>mid)return query(mid+1,r,u<<1|1,ql,qr); else return max(query(l,mid,u<<1,ql,mid),query(mid+1,r,u<<1|1,mid+1,qr)); } }tr; int main() { read(n);tot = n; for(int i=1;i<=n;i++) read(w[i]),ff[i]=i; read(m); for(int x,y,i=1;i<=m;i++) { scanf("%s",op+1); if(op[1]=='U') { read(x),read(y); p[i].op=0,p[i].x=x,p[i].v=y; x = findff(x),y = findff(y); if(x!=y) { int now = ++tot; ff[x]=ff[y]=ff[now]=now; ae(now,x),ae(now,y); } }else if(op[1]=='A') { read(x);if(op[2]!='3')read(y); p[i].op = op[2]-'0',p[i].x = x; if(op[2]!='3')p[i].v = y; }else { if(op[2]!='3')read(x); p[i].op = op[2]-'0'+3; if(op[2]!='3')p[i].x = x; } } for(int i=tot;i>=1;i--)if(!tin[i])dfs(i); tr.build(1,tot,1); for(int i=1;i<=tot;i++)ff[i]=i; for(int i=1,c=n,x;i<=m;i++) { if(!p[i].op) { int x = findff(p[i].x),y = findff(p[i].v); if(x!=y)c++,ff[x]=ff[y]=c; } if(p[i].op==1)tr.insert(1,tot,1,tin[p[i].x],tin[p[i].x],p[i].v); if(p[i].op==2)x=findff(p[i].x),tr.insert(1,tot,1,tin[x],tout[x],p[i].v); if(p[i].op==3)tr.insert(1,tot,1,1,tot,p[i].x); if(p[i].op==4)printf("%d ",tr.query(1,tot,1,tin[p[i].x],tin[p[i].x])); if(p[i].op==5)x=findff(p[i].x),printf("%d ",tr.query(1,tot,1,tin[x],tout[x])); if(p[i].op==6)printf("%d ",tr.query(1,tot,1,1,tot)); } return 0; }