自动搬运

查看原文

来自洛谷，原作者为

	SmokingTurtle https://www.luogu.me/paste/4mvfnsgj || 极少上线（家长原因） || ENTP || 一个可爱的ST表捏~ || 大号：shaozhehan

搬运于2025-08-24 23:09:23，当前版本为作者最后更新于2025-02-04 23:08:20，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

前言

本题属于思维题，本人在结束后 10min 想到了正确做法，写个题解纪念一下。

思路

我们仔细观察题目的两个操作，发现包括了删除节点和加入边，一个是删除一个是加入，不是很好处理，于是思考如何转化。

手动模拟一下样例，我们发现“在节点 $t$ 被移除之前的每对邻居之间添加一条边”这个操作不改变连通性，因此我们可以考虑将这个操作懒标记掉。

具体来说，对于 $s_t=1$ 的情况，我们可以将其变为“将节点 $t$ 假装删除”，使得它依旧维持着连通性，但是不计入答案。

我们现在要处理的操作是删除节点和假装删除节点。由于都是删除类操作，我们将时间逆序，变为加入。

此时，我们的操作变成了将假装删除的点添加回来和添加一个节点。

这个问题显然可以使用并查集来维护。

细节部分

在并查集中，我们重新定义“大小”这个概念，不是指并查集中有多少个点，而是指并查集中有多少个没有被虚假删除的点，这样方便统计答案。

接着，我们考虑加入一个节点的时候它的哪些邻边应该被加入。这当然是当对面的节点已经被加入以后。

具体的，加入节点 $u$ 的时候，对于他的一条邻边 $u\harr v$，这条边被加入当且仅当 $v$ 此时已经在图里。这包含两种情况：要么 $v>u$，要么 $s_v=1$ （$v$ 只是被虚假删除了）。这样我们就不能按秩合并了，但是加上路径压缩，我们依然能够保证时间复杂度在 $O(m \log n)$ 级别，能够通过本题。

概括

总结一下，我们并查集初始每个点是一个集合，但是“大小”为 $0$。接着，倒序遍历每个点，对于他的所有邻边，如果对面的点比自己编号大或者属于虚假删除的点，那么加上这条边。最后，将这个点所在的并查集大小加 $1$。在这个期间维护答案。

$\color{Red}坑点$

1. 如果两个假装删除的点之间有边，那么在开始计算之间就应该加上。

对应的 hack 数据：

4 3
0011
3 1
1 2
2 4

正确答案

6
1
0
0

2. 十年 OI 一场空，不开 long long 见祖宗！

代码时间

本人比较懒，没有加注释，凑合看吧。

代码曾经有防 CTJ。

#include<iostream>
#include<vector>
using namespace std;
int n,m,fa[200005],sz[200005];
long long sum,ans[200005];
vector<int> g[200005];
bool s[200005];
int get(int u){return (u==fa[u])?u:(fa[u]=get(fa[u]));}
void c(int u,int v)
{
	if(get(u)!=get(v))
		u=fa[u],v=fa[v],
		fa[u]=v,
		sum+=(1ll*sz[u]*sz[v]),
		sz[v]+=sz[u]; 
}
void add(int u)
{
	u=get(u);
	sum+=sz[u];
	sz[u]++;
}
int main()
{
	cin>>n>>m;
	char ch;
	for(int i=1;i<=n;i++)
		fa[i]=i,sz[i]=0;
	for(int i=1;i<=n;i++)
		cin>>ch,s[i]=(ch=='1');
	for(int i=1,u,v;i<=m;i++)
	{
		cin>>u>>v;
		g[u].emplace_back(v);
		g[v].emplace_back(u);
		if(s[u] && s[v])
			c(u,v);
	}
	for(int i=n;i>=1;i--)
	{
		for(int j:g[i])
			if(j>i || s[j]==1)
				c(i,j);
		add(i);
		ans[i]=sum;
	}
	for(int i=1;i<=n;i++)
		cout<<ans[i]<<endl;
}

吐槽

那句 “十年 OI 一场空，不开 long long 见祖宗” 由于一开始试图使用 \Huge + \texttt 表示强调，并且忘了加空格，被打回了 $4$ 次，悲

上面这句吐槽因为一开始滥用代码块又被打回了一次，悲