【ACGO巅峰赛#19】T4公告 题解

首先考虑没有退群操作该如何做。

如果把每名学生看做一个点，把同一个群里的所有人都用无向边连接，那么题目就是求 $1$ 号学生所在连通块的大小。这显然是并查集的经典应用。于是我们给每个群的学生连接起来求并查集的大小即可。注意并不需要每两个学生都连接一次，会超时。我们可以选择每个群第一个学生为父节点，其他学生全部向父节点连边。

加入删边（即退群）操作后，并查集显然无法做到删边的功能（期待有神犇能搞个可持久化并查集来打脸我bushi）。但是如果我们离线处理询问，将删边操作倒过来，不就是加边了？于是我们将删边操作倒序枚举，每遇到一次删边就反过来加边，同时将答案存起来倒序输出，就可以使用并查集做到了。

注意细节：由于倒序后一开始处理的情况是所有能退群的学生都退群后的，所以我们加边时需要检查：如果当前群里枚举到的这个学生在退群操作中出现过，那么不能把他加入群里。这样有可能第一个学生不能在一开始就被加入群中，因此每个群的父节点应改为第一个加入群的学生。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5+10;
int n,m,a[N];
int ans[N];
int fa[N],size[N];
int op1[N],op2[N],idx;
int tag[N];
vector<int> vec[N],g[N]; // vec[i]表示第i个群，g[i][j]表示第i个群的第j个学生是否能够加入群中（即未在退群操作中出现过） 
int q;

inline int find(int x){
	if(fa[x]==x) return x;
	return fa[x] = find(fa[x]);
}
inline void merge(int x,int y){
	int fx = find(x);
	int fy = find(y);
	if(fx==fy) return;
	size[fy] += size[fx];
	fa[fx] = fy;
}

signed main(){
	ios::sync_with_stdio(false);
	cin>>n>>m>>q;
	int q1,q2;
	for(int i=1;i<=n;i++) fa[i] = i,size[i] = 1;
	for(int i=1;i<=m;i++){
		cin>>q1;
		vec[i].push_back(0);
		g[i].push_back(0);
		for(int j=1;j<=q1;j++){
			cin>>q2;
			vec[i].push_back(q2);
			g[i].push_back(1);
		}
		sort(vec[i].begin(),vec[i].end()); // sort方便查找某群中的指定学生，将其设定为不可加入 
	}
	for(int i=1;i<=q;i++){
		cin>>q1>>q2;
		op1[i] = q1,op2[i] = q2;
		int num = lower_bound(vec[q2].begin(),vec[q2].end(),q1)-vec[q2].begin(); // 二分查找到某个学生并使得他在g数组对应位置被标记为不可加入 
		g[q2][num] = 0;
	}
	for(int i=1;i<=m;i++){
		int lim = vec[i].size();
		for(int j=1;j<lim;j++){
			if(g[i][j]==0) continue; // 如果这个学生不可加入，则continue掉 
			int v = vec[i][j];
			if(!tag[i]){
				tag[i] = v;
			}
			else{
				merge(tag[i],v);
			}
		}
	}
	for(int i=q;i>=1;i--){
		ans[i] = n-size[find(1)]; 
		q1 = op1[i],q2 = op2[i];
		if(!tag[q2]){
			tag[q2] = q1;
		}
		else{
			merge(tag[q2],q1);
		}
	}
	for(int i=1;i<=q;i++){
		cout<<ans[i]<<endl;
	}
	
	return 0;
}