自动搬运

查看原文

来自洛谷，原作者为

	周子衡 Shadow is the light!

搬运于2025-08-24 22:27:43，当前版本为作者最后更新于2021-03-29 17:19:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考虑维护最后图中极大团，也就是所有的点集 $S$，满足对于 $S$ 中的任意两点 $u,v$，在举办活动后既有 $u\rightarrow v$ 的边，也有 $v\rightarrow u$ 的边。我们先来分析一下一个大小为 $s$ 的极大团给答案带来的贡献：

• 极大团内部有 $s(s-1)$ 条边；
• 对于每个向该团中连了至少一条边的团外的点，该点最后会和团中所有人连单向边。因而如果该团被 $k$ 个点连向，将会给答案带来 $sk$ 的贡献。注意：这里的 $k$ 是连向该团的不同点数，不是连向该团的团数。

我们考虑在加边过程中，用并查集维护每个极大团，并对每个极大团 $S$，动态维护集合：

• $\mathrm{IN}(S)$：向 $S$ 有连边的团的集合；
• $\mathrm{IP}(S)$：向 $S$ 有连边的点的集合；
• $\mathrm{OUT}(S)$：$S$ 连向的团的集合。

当每次加入边 $x\rightarrow y$ 时，设 $x$ 在团 $X$ 中，$y$ 在团 $Y$ 中，如果 $Y$ 之前向 $X$ 连过边，那么我们需要把 $X,Y$ 合并。为了确保时间复杂度，采用启发式合并的技巧。注意一次合并可能会引起其他的合并，使用队列来维护所有的合并即可。如果 $Y$ 之前未向 $X$ 连过边，我们简单地更新即可。注意要去掉集合中的重复元素，可以采用 std::set 实现。总时间复杂度 $O(m\log^2 m)$。

#include<cstdio>
#include<set>
#include<queue>

using namespace std;

struct BCJ
{
	int fa[200000];
	void init(int n){for(int i=1;i<=n;i++)fa[i]=i;}
	int fnd(int x){return x==fa[x]?x:fa[x]=fnd(fa[x]);}
}B;

set<int> IN[200000],OUT[200000],IP[200000],S[200000];
queue<pair<int,int> > Q;

long long calc(int x){return (long long)(S[x].size()-1)*S[x].size()+(long long)IP[x].size()*S[x].size();}
long long ans;

typedef set<int>::iterator IT;

void merge(int x,int y)
{
	x=B.fnd(x),y=B.fnd(y);if(x==y)return;
	if(S[x].size()<S[y].size())swap(x,y);
	B.fa[y]=x;
	ans-=calc(x),ans-=calc(y);
	if(IN[x].count(y))IN[x].erase(y);
	if(OUT[x].count(y))OUT[x].erase(y);
	for(IT it=S[y].begin();it!=S[y].end();it++)
	{
		int u=*it;S[x].insert(u);
		if(IP[x].count(u))IP[x].erase(u);
	}
	for(IT it=IP[y].begin();it!=IP[y].end();it++)
	{
		int u=*it;if(!IP[x].count(u)&&!S[x].count(u))IP[x].insert(u);
	}
	for(IT it=IN[y].begin();it!=IN[y].end();it++)
	{
		int u=*it;if(u==x)continue;
		OUT[u].erase(y),OUT[u].insert(x);IN[x].insert(u);
		if(OUT[x].count(u))Q.push(make_pair(x,u));
	}
	for(IT it=OUT[y].begin();it!=OUT[y].end();it++)
	{
		int u=*it;if(u==x)continue;
		IN[u].erase(y),IN[u].insert(x);OUT[x].insert(u);
		if(IN[x].count(u))Q.push(make_pair(x,u));
	}
	ans+=calc(x);
}
void work()
{
	while(!Q.empty())
	{
		int x=Q.front().first,y=Q.front().second;Q.pop();
		merge(x,y);
	}
}

int main()
{
	int n=0,m=0;scanf("%d%d",&n,&m);B.init(n);
	for(int i=1;i<=n;i++)S[i].insert(i);
	for(int i=1;i<=m;i++)
	{
		int x=0,y=0;scanf("%d%d",&x,&y);
		int fx=B.fnd(x),fy=B.fnd(y);if(fx==fy){printf("%lld\n",ans);continue;}
		if(IN[fx].count(fy))
		{
			Q.push(make_pair(fx,fy));work();
		}
		else
		{
			ans-=calc(fx),ans-=calc(fy);
			IN[fy].insert(fx),IP[fy].insert(x),OUT[fx].insert(fy);
			ans+=calc(fx),ans+=calc(fy);
		}
		printf("%lld\n",ans);
	}
}