本文涉及知识点

C++差分数组

P9583涂色

n行m列方格纸，初始是白色(0层)。共涂色q次，每次选择一行或一列，将这行或列涂一层颜色。如果某次涂色后，某个单格是k层颜色，则涂为白色(0层）。求最后被涂色的单格数量。color[i] = {typei,xi},typei为1，给xi行涂色。typei为2，给xi列涂色。xi从1开始。
1 <=m,n <=2e5 1 <= k <= q <=5e5

差分数组

rcnt[i]记录，按行涂i次的行数。i$\in$[0,n]。
ccnt[i]记录，按列涂i次的列数。i$\in$[0,m]。
计算rcnt的过程
rtmp[i]记录，第i行被涂的次数。i$\in$[0,n)。
计算ccnt类似。
每次涂色后，将k层颜色涂成0层。等同于结束后，将k的倍数层颜色涂成0层。故只需要记录 被涂次数%k。

分类讨论

某行按行涂0次，则本行符合条件的单格数：ccnt[1…m]-cnt[k]
令某行被涂 x次，x > 0 则当前行符合单格数：
{ m − c n t [ k − x ] k − x > = 0 m o t h e r \begin{cases} m - cnt[k-x] && k-x >=0 \\ m && other\\ \end{cases} {m−cnt[k−x]m​​k−x>=0other​

代码

核心代码

#include <iostream>
#include <sstream>
#include <vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<string>
#include<algorithm>
#include<functional>
#include<queue>
#include <stack>
#include<iomanip>
#include<numeric>

#include <bitset>
using namespace std;

class Solution {
		public:
			long long Cal(const int R, const int C, const int K, vector<vector<int>>& color) {
				vector<int> rtmp(R), ctmp(C);
				for (const auto& v : color) {
					if (1 == v[0]) {
						rtmp[v[1] - 1]++;
					}
					else {
						ctmp[v[1] - 1]++;
					}
				}
				auto ToCnt = [&](const vector<int>& tmp) {
					vector<int> ret(K);
					for (const auto& n : tmp) {
						ret[n % K]++;
					};
					return ret;
				};
				auto rcnt = ToCnt(rtmp);
				auto ccnt = ToCnt(ctmp);
				long long ret =0;//按行涂0次
				for (int i = 0; i < rcnt.size(); i++) {
					ret += ((long long)C - ccnt[(K - i) % K]) * rcnt[i];
				}
				return ret;
			}
		};

int main() {
	//freopen("./a.in", "r", stdin);
	//freopen("./output.txt", "a", stdout);

	int R,C,Q1,K;
	scanf("%d%d%d%d", &R, &C, &Q1, &K);
	vector<vector<int>> color(Q1,vector<int>(2) );	
	for (int i = 0; i < Q1; i++) {
		scanf("%d%d", &color[i][0],&color[i][1]);
	}	
	
	auto res = Solution().Cal(R, C, K, color);
	printf("%lld", res);
	return 0;
}

单元测试

int R, C, K;
		vector<vector<int>> color;
		TEST_METHOD(TestMethod1)
		{
			R = 2, C = 3, K = 2, color = { {1,1},{1,2},{1,1} };
			auto res = Solution().Cal(R,C,K,color);
			AssertEx(3LL, res);
		}
		TEST_METHOD(TestMethod2)
		{
			R = 2, C = 3, K = 2, color = { {1,1},{2,1} };
			auto res = Solution().Cal(R, C, K, color);
			AssertEx(3LL, res);
		}
		TEST_METHOD(TestMethod3)
		{
			R = 2, C = 3, K = 2, color = { {2,1},{2,2},{2,3} };
			auto res = Solution().Cal(R, C, K, color);
			AssertEx(6LL, res);
		}
		TEST_METHOD(TestMethod11)
		{
			R = 3, C = 4, K = 3, color = { {1, 3}, { 2,4 }, { 1,2 }, { 1,3 }, { 2,2 } };
			auto res = Solution().Cal(R, C, K, color);
			AssertEx(8LL, res);
		}