错误の桶解法 - 洛谷保存站

# 桶の桶解法

我们考虑特殊性质 A。

开两个桶 $row, col$，其中 $row_i$ 表示第 $i$ 行被涂色了多少次，$col_i$ 表示第 $i$ 列被涂色了多少次。

这样，由于只涂行，只需判断每个 $row_i$ 是否满足 $row_i \bmod k$ 不为 $0$ 即可。如果满足条件，则将结果加上 $m$。

如下所示：
```cpp
int main() {
	read(n), read(m), read(q), read(k);
	while (q--) {
		read(opt), read(x);
		if (opt == 1) row[x]++;
		else col[x]++;
	}
	long long res = 0;
	bool flag = true;
	for (int i = 1; i <= m; i++) {
		if (col[i] >= 1) {
			flag = false;
			break;
		} 
	}   // 特判性质A
	if (flag) {
		for (int i = 1; i <= n; i++) {
			if (row[i] % k) res += m;
		}
		printf("%lld", res);
		return 0;
	}
}
```

现在考虑将这个思路延展到一般情况。我们发现，对于每个点 $(i, j)$，只要 $(row_i+col_i) \bmod k$ 不为 $0$，就可以累加到答案上。

然而这样的复杂度是 $O(q+nm)$ 的，我们考虑优化。

开两个桶 $rcnt, ccnt$ 对 $row, col$ 计数。

为什么要开桶の桶呢？这里涉及到 $row, col$ 的顺序对答案无影响。

于是，就可以这样了：
```cpp
int q, opt, x;
long long n, m, k, row[N], col[N];
map<int, long long> rcnt, ccnt;

int main() {
	read(n), read(m), read(q), read(k);
	while (q--) {
		read(opt), read(x);
		if (opt == 1) row[x]++;
		else col[x]++;
	}
	long long res = 0;
	bool flag = true;
	for (int i = 1; i <= m; i++) {
		if (col[i] >= 1) {
			flag = false;
			break;
		} 
	}
	if (flag) {
		for (int i = 1; i <= n; i++) {
			if (row[i] % k) res += m;
		}
		printf("%lld", res);
		return 0;
	}

for (int i = 1; i <= n; i++) rcnt[row[i]]++;
	for (int i = 1; i <= m; i++) ccnt[col[i]]++;
	for (int i = 1; i <= n; i++) {
		for (const auto& j : ccnt) {
			if ((row[i] + j.first) % k) res += j.second;
		}
	}
	printf("%lld", res);
	return 0;
}
```
然而这样还可能超时，考虑根据 size 交换。

我们希望 $ccnt$ 的 size 尽可能小，同时注意交换 $n, m$ 以及 $row, col$。
```cpp
if (ccnt.size() > rcnt.size()) {
	swap(ccnt, rcnt);
	swap(n, m);
	swap(row, col);
}
```
于是，可以放上赛时 AC Code 了：
```cpp
#include <bits/stdc++.h>
#define N 200005
using namespace std;

template <typename T>
inline void read(T& x) {
	x = 0;
	int t = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		if (ch == '-') t = -1;
		ch = getchar();
	}
	while ('0' <= ch && ch <= '9') {
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	x *= t;
}

int q, opt, x;
long long n, m, k, row[N], col[N];
map<int, long long> rcnt, ccnt;

for (int i = 1; i <= n; i++) rcnt[row[i]]++;
	for (int i = 1; i <= m; i++) ccnt[col[i]]++;
	if (ccnt.size() > rcnt.size()) {  // 我们希望ccnt的size尽可能小
		swap(ccnt, rcnt);
		swap(n, m);
		swap(row, col);
	}
	for (int i = 1; i <= n; i++) {
		for (const auto& j : ccnt) {
			if ((row[i] + j.first) % k) res += j.second;
		}
	}
	printf("%lld", res);
	return 0;
}
```
复杂度玄学，但可以通过本题。

原因：想要卡掉这种做法，需要构造类似 $row_i = i$ 的数据，然而如果这样构造，在 $q$ 次修改中，$n \le \dfrac{q(q + 1)}{2}$，即 $O(\sqrt{n})$。

所以，本方法的最坏复杂度是 $O(q+\min(m\sqrt{n}, n\sqrt{m}))$（因为我们采用了按 size 交换），常数较小 + 吸氧 + 洛谷神机 + 水数据可以通过。

正在渲染内容...