http://www.lydsy.com/JudgeOnline/problem.php?id=2333
读入所有数据，先模拟一遍所有的合并操作
我们不关心联通块长什么样，只关心联通块内有谁
所以可以把一个联通块用一个链表存储
合并x和y时，y的链表整体接到x的链表后面
这样就成了线性结构
按照链表顺序重新给序列标号即可用线段树维护
一遍过，^_^
#include<cstdio> #include<iostream> #include<algorithm> using namespace std; #define N 300001 int a[N]; struct Data { char s[3]; int x,y; }data[N]; int fa[N],nxt[N],ed[N]; int id[N],dy[N]; int mx[N<<2],f[N<<2]; int ans; void read(int &x) { x=0; int f=1; char c=getchar(); while(!isdigit(c)) { if(c=='-') f=-1; c=getchar(); } while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); } x*=f; } void build(int k,int l,int r) { if(l==r) { mx[k]=a[id[l]]; return; } int mid=l+r>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r); mx[k]=max(mx[k<<1],mx[k<<1|1]); } void down(int k) { mx[k<<1]+=f[k]; mx[k<<1|1]+=f[k]; f[k<<1]+=f[k]; f[k<<1|1]+=f[k]; f[k]=0; } void add(int k,int l,int r,int opl,int opr,int w) { if(l>=opl && r<=opr) { f[k]+=w; mx[k]+=w; return; } if(f[k]) down(k); int mid=l+r>>1; if(opl<=mid) add(k<<1,l,mid,opl,opr,w); if(opr>mid) add(k<<1|1,mid+1,r,opl,opr,w); mx[k]=max(mx[k<<1],mx[k<<1|1]); } void query(int k,int l,int r,int opl,int opr) { if(l>=opl && r<=opr) { ans=max(ans,mx[k]); return; } if(f[k]) down(k); int mid=l+r>>1; if(opl<=mid) query(k<<1,l,mid,opl,opr); if(opr>mid) query(k<<1|1,mid+1,r,opl,opr); } int find(int i) { return fa[i]==i ? i : fa[i]=find(fa[i]); } int main() { int n,m; read(n); for(int i=1;i<=n;++i) read(a[i]); for(int i=1;i<=n;++i) fa[i]=i,ed[i]=i; char s[5]; int x,y; int fx,fy; read(m); for(int i=1;i<=m;++i) { scanf("%s",data[i].s); if(!(data[i].s[0]=='F' && data[i].s[1]=='3')) read(data[i].x); if(data[i].s[0]=='U' || data[i].s[0]=='A' && data[i].s[1]!='3') read(data[i].y); if(data[i].s[0]=='U') { fx=find(data[i].x); fy=find(data[i].y); nxt[ed[fx]]=fy; ed[fx]=ed[fy]; fa[fy]=fx; } } int tot=0; for(int i=1;i<=n;++i) if(find(i)==i) { int j=i; while(j!=ed[i]) { id[++tot]=j; dy[j]=tot; j=nxt[j]; } id[++tot]=j; dy[j]=tot; } build(1,1,n); for(int i=1;i<=n;++i) fa[i]=i,ed[i]=i; int all=0; for(int i=1;i<=m;++i) { if(data[i].s[0]=='U') { fx=find(data[i].x); fy=find(data[i].y); nxt[ed[fx]]=fy; ed[fx]=ed[fy]; fa[fy]=fx; } else if(data[i].s[0]=='A') { if(data[i].s[1]=='1') add(1,1,n,dy[data[i].x],dy[data[i].x],data[i].y); else if(data[i].s[1]=='2') add(1,1,n,dy[find(data[i].x)],dy[ed[find(data[i].x)]],data[i].y); else all+=data[i].x; } else { if(data[i].s[1]=='1') { ans=-1e9; query(1,1,n,dy[data[i].x],dy[data[i].x]); printf("%d ",ans+all); } else if(data[i].s[1]=='2') { ans=-1e9; query(1,1,n,dy[find(data[i].x)],dy[ed[find(data[i].x)]]); printf("%d ",ans+all); } else printf("%d ",mx[1]+all); } } }