自动搬运

查看原文

来自洛谷，原作者为

	BL_zhanggezi 新主页：https://www.luogu.com.cn/article/5hqywm8j

搬运于2025-08-24 22:49:50，当前版本为作者最后更新于2023-08-27 09:30:37，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目大意

原本所有方格都是空白的，每次涂色给一行或一列的所有方格都添加 $1$ 层颜色，**每次涂色结束后，把所有被涂上 $k$ 层颜色的方格的颜色都擦掉，让这些方格都变成空白的。**问最终共有多少方格被涂上了颜色。

思路

首先我们可以想到一种办法：二维差分。但是当我们看 $n$ 和 $m$ 的范围时我们会发现如果开二维数组会爆，所以我们可以开两个一维数组 $h$ 和 $s$ 来分别储存行和列被涂过的次数。

但开两个一维数组似乎只能使用暴力，因为我们需要求出每个方格被涂过的次数然后看看能否整除 $k$，这样还会超时。

是否能在此想法上优化？当然可以。我们可以用 $c$ 来保存如需把放个方格变成空白的 $h_i \bmod k$ 的值，而 $c=c-(s_i \bmod k) \bmod k$，所以我们可以使用循环来计算满足 $h_i \bmod k = c$ 的数量，而一段满足条件的 $h_i$ 可以使用二分查找数量，使用二分前要将 $h$ 从小到大排序，该部分代码如下（其中 $ans$ 的初始值为 $n \times m$，让 $ans$ 减去空白方格的数量就可以得出最终答案）：

for(int i=1;i<=m;i++)
{
	c=s[i]%k;
	for(int j=(k-c)%k;j<=h[n];j+=k)//每次加k优化
	{
		ans=ans-(find_right(j)-find_left(j)+1);
      		//find_right(j)-find_left(j)+1是符合要求的数量
	}
}

当我们使用这种方法去写时，运行第四个样例时我们会发现它超时了。我们把超时的原因锁定在二分上，新的问题出现了：如何优化二分？

我们可以想想我们使用二分是用来干什么的？对，是求 $h_i = c$ 数量，所以我们可以使用数组计数进行优化。优化后的部分代码如下：

for(int i=1;i<=m;i++)
{
	c=s[i]%k;
	for(int j=(k-c)%k;j<=h[n];j+=k)
	{
		ans=ans-ss[j];//ss[j]是符合要求的数量
	}
}

完整 AC 代码如下：

#include<bits/stdc++.h>
using namespace std;
long long n,m,nm,k,as,x,h[200010],s[200010],ans=0,c,ss[500010];
int main()
{
	cin>>n>>m>>nm>>k;
	ss[0]=n;//初始化，开始时每个格子都没涂，所以没涂的行数有n 
	for(int i=1;i<=nm;i++)
	{
		cin>>as>>x;
		if(as==1) 
		{
			h[x]++;
			ss[h[x]-1]--;//涂过h[x]-1次的行数减1 
			ss[h[x]]++;//涂过h[x]次的行数加1 
		} 
		else s[x]++;
	}
	sort(h+1,h+n+1);//从小到大排序 
	ans=n*m;//答案初始化 
	for(int i=1;i<=m;i++)
	{
		c=s[i]%k;
		for(int j=(k-c)%k;j<=h[n];j+=k)
		{
			ans=ans-ss[j];
		}
	}//该部分解释同上推理过程 
	cout<<ans;//输出结果 

	return 0;
}

注意事项

使用 int 会爆，所以请使用 long long。