线段树+并查集，对于每个操作我们只需要维护他在自己子树中的最值和在整个树里的最值，类似于线段树动态开点。
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=300005; 4 int n,m,cnt,sum,inf=1e9+7,f[N],a[N],ans[N*4]; 5 struct node 6 { 7 int lz,mx,l,r; 8 }t[N*20]; 9 int size[N],rt[N]; 10 char s[10]; 11 inline int get(int x){return x==f[x]?x:f[x]=get(f[x]);} 12 void pushdown(int x) 13 { 14 if(t[x].lz) 15 { 16 if(t[x].l) 17 { 18 t[t[x].l].mx+=t[x].lz; 19 t[t[x].l].lz+=t[x].lz; 20 } 21 if(t[x].r) 22 { 23 t[t[x].r].mx+=t[x].lz; 24 t[t[x].r].lz+=t[x].lz; 25 } 26 t[x].lz=0; 27 } 28 } 29 void merge(int &x,int &y,int l,int r) 30 { 31 if(!y){y=x;return;} 32 if(!x)return; 33 int mid=(l+r)>>1; 34 pushdown(x);pushdown(y); 35 merge(t[x].l,t[y].l,l,mid); 36 merge(t[x].r,t[y].r,mid+1,r); 37 t[y].mx=max(t[t[y].l].mx,t[t[y].r].mx); 38 } 39 int query(int p,int l,int r,int x) 40 { 41 if(l==r)return t[p].mx; 42 pushdown(p); 43 int mid=(l+r)>>1; 44 if(x<=mid)return query(t[p].l,l,mid,x); 45 else return query(t[p].r,mid+1,r,x); 46 } 47 void change(int &p,int l,int r,int x,int y) 48 { 49 if(!p)p=++cnt; 50 if(l==r){t[p].mx+=y;return;} 51 pushdown(p); 52 int mid=l+r>>1; 53 if(x<=mid)change(t[p].l,l,mid,x,y); 54 else change(t[p].r,mid+1,r,x,y); 55 t[p].mx=max(t[t[p].l].mx,t[t[p].r].mx); 56 } 57 void tmax(int p,int l,int r,int x,int y) 58 { 59 if(l==r){ans[p]=y;return ;} 60 int mid=(l+r)>>1; 61 if(x<=mid)tmax(p<<1,l,mid,x,y); 62 else tmax(p<<1|1,mid+1,r,x,y); 63 ans[p]=max(ans[p<<1],ans[p<<1|1]); 64 } 65 int main() 66 { 67 scanf("%d",&n);int x,y; 68 t[0].mx=-inf; 69 for(int i=1;i<=n;++i) 70 { 71 scanf("%d",&a[i]); 72 tmax(1,1,n,i,a[i]); 73 f[i]=i;size[i]=1; 74 change(rt[i],1,n,i,a[i]); 75 } 76 scanf("%d",&m); 77 for(int i=1;i<=m;++i) 78 { 79 scanf("%s",s); 80 if(s[0]=='U') 81 { 82 scanf("%d%d",&x,&y); 83 int fx=get(x);int fy=get(y); 84 if(fx==fy)continue; 85 if(size[fx]>size[fy])swap(fx,fy); 86 size[fy]+=size[fx];f[fx]=fy; 87 merge(rt[fx],rt[fy],1,n); 88 tmax(1,1,n,fy,t[rt[fy]].mx); 89 tmax(1,1,n,fx,-inf); 90 } 91 else if(s[0]=='A') 92 { 93 if(s[1]=='1') 94 { 95 scanf("%d%d",&x,&y); 96 int fx=get(x); 97 change(rt[fx],1,n,x,y); 98 tmax(1,1,n,fx,t[rt[fx]].mx); 99 } 100 else if(s[1]=='2') 101 { 102 scanf("%d%d",&x,&y); 103 int fx=get(x); 104 t[rt[fx]].lz+=y;t[rt[fx]].mx+=y; 105 tmax(1,1,n,fx,t[rt[fx]].mx); 106 } 107 else scanf("%d",&y),sum+=y; 108 } 109 else 110 { 111 if(s[1]=='1') 112 { 113 scanf("%d",&x); 114 int fx=get(x); 115 printf("%d ",query(rt[fx],1,n,x)+sum); 116 } 117 else if(s[1]=='2') 118 { 119 scanf("%d",&x); 120 int fx=get(x); 121 printf("%d ",t[rt[fx]].mx+sum); 122 } 123 else 124 { 125 printf("%d ",sum+ans[1]); 126 } 127 } 128 } 129 return 0; 130 }