題目鏈接：點擊查看

題目大意：有 n 個球員和 m 個球迷，一個球員可能是多個球迷的粉絲，需要選擇最少的球員進行比賽，使得所有的球迷都愿意觀看（對于每個球迷來說，都有至少一個其喜歡的球員入選比賽）

對于球迷與球員之間的關系，如果球迷?a 喜歡球員 b ，且球迷 c 喜歡球迷 b ，那么球迷 a 也會喜歡球迷 c 所喜歡的其他球員，對于球迷 c 同理

現在有 q 次粉絲關系的修改（增加或刪除），對于每次修改后回答詢問

題目分析：畫畫圖不難看出，球迷與球員連邊，設 cnt 為總的連通塊的個數，設 cntn 為有多少個孤立的球員，cntm 有多少個孤立的球迷，舉個例子：

上圖的關系中，cnt = 3 , cntn = 1 , cntm = 0

對于每次詢問，如果 cntm > 0 的話，意思就是有 cntm 個球迷沒有喜歡的球員，答案顯然為 -1 ，除此之外，答案都為 cnt - cntn

這樣的話題目就轉換為了維護一個并查集的關系就好了，但是并查集需要支持增加和刪除操作，如果只需要維護一個 cnt 變量的話，直接用并查集的刪除這個算法足夠，但同時還需要維護 cntn 和 cntm ，用并查集的刪除就不太好維護了

這里先說一下 cntn 和 cntm 該如何維護吧，因為每次連邊一定是球迷連向球員的一條邊，假設 x 為球迷，y 為球員：

添加 ( x , y ) 這條邊：

如果 x 之前是孤立的球迷，則連通后 cntm 減一

如果 y 之前是孤立的球員，則連通后 cntn?減一

刪除 ( x , y ) 這條邊：

如果 x 之后是孤立的球迷，則連通后 cntm 加一

如果 y 之后是孤立的球員，則連通后 cntn 加一

既然不能用并查集的刪除，那么可以換一個方向思考，刪除一條邊等于撤銷這條邊，所以我們可以使用并查集按秩合并中的撤銷操作來表示刪除（其實就是用棧維護一下合并的信息，撤銷的時候再邊出棧邊撤銷就好了）

鑒于這個題目允許離線操作，可以用線段樹分治來實現，線段樹的下標作為時間單位，這樣每個葉子結點就代表了每個詢問，遞歸的時候用并查集維護一下聯通性就好了

時間復雜度應該是 qlogq * log( n + m )，因為并查集是按秩合并的，每次查詢需要 log n 的時間復雜度

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=4e5+100;map<int,int>pre[N];int f[N],rk[N],ans[N],cnt,cntn,cntm;struct revo {int cnt,cntn,cntm;int fax,fay;int rkx,rky; };struct Node {int l,r;vector<pair<int,int>>node;//位于[l,r]這段時間內的邊有哪些vector<revo>st;//并查集的撤銷用 }tree[N<<2];int find(int x) {return f[x]==x?x:find(f[x]); }revo merge(int x,int y)//并查集的合并，返回合并之前的信息revo用于撤銷 {revo ans;int xx=find(x),yy=find(y);ans.cnt=cnt,ans.cntm=cntm,ans.cntn=cntn;ans.fax=xx,ans.fay=yy;ans.rkx=rk[xx],ans.rky=rk[yy];if(xx!=yy){if(rk[xx]==1)cntm--;if(rk[yy]==1)cntn--;cnt--;if(rk[xx]>rk[yy])swap(xx,yy);f[xx]=yy;rk[yy]=max(rk[yy],rk[xx]+1);}return ans; }void revocation(revo node)//并查集的撤銷，將并查集恢復至node狀態 {cnt=node.cnt;cntn=node.cntn;cntm=node.cntm;f[node.fax]=node.fax;f[node.fay]=node.fay;rk[node.fax]=node.rkx;rk[node.fay]=node.rky; }void build(int k,int l,int r) {tree[k].l=l;tree[k].r=r;if(l==r)return;int mid=l+r>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r); }void update(int k,int l,int r,pair<int,int>val) {if(l>r)return;if(tree[k].l>r||tree[k].r<l)return;if(tree[k].l>=l&&tree[k].r<=r){tree[k].node.push_back(val);return;}update(k<<1,l,r,val);update(k<<1|1,l,r,val); }void dfs(int k)//線段樹分治 {for(auto it:tree[k].node)//并查集的合并tree[k].st.push_back(merge(it.first,it.second));if(tree[k].l==tree[k].r){if(cntm>0)ans[tree[k].l]=-1;elseans[tree[k].l]=cnt-cntn;}else{dfs(k<<1);dfs(k<<1|1);}while(tree[k].st.size())//并查集的撤銷{revocation(tree[k].st.back());tree[k].st.pop_back();} }void init() {for(int i=1;i<N;i++){f[i]=i;rk[i]=1;} }int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);init();int n,m,q;//n:球員 m:球迷 edge:m->nscanf("%d%d%d",&n,&m,&q);cnt=n+m,cntn=n,cntm=m;build(1,1,q);for(int i=1;i<=n;i++){int k;scanf("%d",&k);while(k--){int x;scanf("%d",&x);pre[x][i]=1;}}for(int i=1;i<=q;i++){int a,b;scanf("%d%d",&a,&b);if(!pre[a].count(b))pre[a][b]=i;else{update(1,pre[a][b],i-1,make_pair(a+n,b));pre[a].erase(b);}}for(int i=1;i<=m;i++)for(auto it:pre[i])update(1,it.second,q,make_pair(i+n,it.first));dfs(1);for(int i=1;i<=q;i++)printf("%d\n",ans[i]);return 0; }

?

總結

以上是生活随笔為你收集整理的牛客多校8 - All-Star Game(线段树分治+并查集按秩合并的撤销操作)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。