正題

題目鏈接:https://www.luogu.com.cn/problem/P3273

---

題目大意

$n$個點有權(quán)值，要求支持操作

連接兩個點

單點加權(quán)

聯(lián)通塊加權(quán)

全圖加權(quán)

單點詢問

聯(lián)通塊詢問最大值

全圖詢問最大值

---

解題思路

把所有可能產(chǎn)生的聯(lián)通塊都變到一個區(qū)間里就好了

考慮怎么排這個東西，可以先離線，每次加邊的時候連接兩個聯(lián)通塊根，這樣跑出來的$dfs$序就是符合要求的。

注意因為鄰接表是按照加邊的順序倒著枚舉的，所以要反過來加邊。

然后用線段樹直接維護答案就好了

時間復(fù)雜度$O(n\log n)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=3e5+10; struct qnode{char op[3];int x,y; }p[N]; struct node{int to,next; }a[N]; int n,q,tot,cnt,ls[N],w[N],fa[N],l[N],r[N]; struct SegTree{int w[N<<2],lazy[N<<2];void Downdata(int x){if(!lazy[x])return;w[x*2]+=lazy[x];lazy[x*2]+=lazy[x];w[x*2+1]+=lazy[x];lazy[x*2+1]+=lazy[x];lazy[x]=0;return;}void Change(int x,int L,int R,int l,int r,int val){if(L==l&&R==r){w[x]+=val;lazy[x]+=val;return;}int mid=(L+R)>>1;Downdata(x);if(r<=mid)Change(x*2,L,mid,l,r,val);else if(l>mid)Change(x*2+1,mid+1,R,l,r,val);else Change(x*2,L,mid,l,mid,val),Change(x*2+1,mid+1,R,mid+1,r,val);w[x]=max(w[x*2],w[x*2+1]);return;}int Ask(int x,int L,int R,int l,int r){if(L==l&&R==r){return w[x];}int mid=(L+R)>>1;Downdata(x);if(r<=mid)return Ask(x*2,L,mid,l,r);if(l>mid)return Ask(x*2+1,mid+1,R,l,r);return max(Ask(x*2,L,mid,l,mid),Ask(x*2+1,mid+1,R,mid+1,r));} }T; void addl(int x,int y){if(x==y)return;a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;return; } int find(int x) {return (fa[x]==x)?x:(fa[x]=find(fa[x]));} void dfs(int x){l[x]=r[x]=++cnt;T.Change(1,1,n,cnt,cnt,w[x]);for(int i=ls[x];i;i=a[i].next)dfs(a[i].to);return; } int main() {scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&w[i]),fa[i]=i;scanf("%d",&q);for(int i=1;i<=q;i++){scanf("%s",p[i].op);if(p[i].op[0]=='U'){scanf("%d%d",&p[i].x,&p[i].y);p[i].x=find(p[i].x);p[i].y=find(p[i].y);if(p[i].x==p[i].y)continue;if(p[i].x<p[i].y)swap(p[i].x,p[i].y);fa[p[i].y]=p[i].x;}else if(p[i].op[0]=='A'&&p[i].op[1]=='1')scanf("%d%d",&p[i].x,&p[i].y);else if(p[i].op[0]=='A'&&p[i].op[1]=='2')scanf("%d%d",&p[i].x,&p[i].y);else if(p[i].op[0]!='F'||p[i].op[1]!='3')scanf("%d",&p[i].x);}for(int i=q;i>=1;i--)if(p[i].op[0]=='U')addl(p[i].x,p[i].y);for(int i=1;i<=n;i++)if(find(i)==i)dfs(i);for(int i=1;i<=n;i++)fa[i]=i;for(int i=1;i<=q;i++){int x=p[i].x,y=p[i].y;if(p[i].op[0]=='U'){if(x==y)continue;fa[y]=x;r[x]=r[y];}else if(p[i].op[0]=='A'&&p[i].op[1]=='1')T.Change(1,1,n,l[x],l[x],y);else if(p[i].op[0]=='A'&&p[i].op[1]=='2')x=find(x),T.Change(1,1,n,l[x],r[x],y);else if(p[i].op[0]=='A'&&p[i].op[1]=='3')T.Change(1,1,n,1,n,x);else if(p[i].op[0]=='F'&&p[i].op[1]=='1')printf("%d\n",T.Ask(1,1,n,l[x],l[x]));else if(p[i].op[0]=='F'&&p[i].op[1]=='2')x=find(x),printf("%d\n",T.Ask(1,1,n,l[x],r[x]));else printf("%d\n",T.Ask(1,1,n,1,n));}return 0; } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的P3273-[SCOI2011]棘手的操作【线段树,并查集】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。