解法
题中说求最终有多少个方格涂着颜色，那我们可以求有多少个方格没有颜色，用方格的总数减去没有颜色的方格数即为所求。
考虑本题涂色规律，涂上 $k$ 层颜料的方格其颜料会被擦去，这种操作的本质是对 $k$ 取模，所以没有颜色的方格即该方格所在的行、列被涂色的次数和可以被 $k$ 整除。
现在分别统计每个行、每个列的涂色次数，然后对行、列分别开两个桶，维护每行、每列的涂色次数对 $k$ 取模后的值。
然后枚举桶里的元素。设有 $rubh_i$ 个行的涂色次数对 $k$ 取模等于 $i$，$rubl_i$ 个列的涂色次数对 $k$ 取模等于 $i$，则想要让一个方格没有颜色，则必须满足 $hang_i + lie_i \equiv 0 \pmod{k}$，所以对于 $rubh_i$ 个行，只有 $rubl_{k-i}$ 个列与之匹配才能是没有颜色的方格，根据乘法原理，有 $rubh_i \times rubl_{k-i}$ 个方格没有颜色。特殊地，$rubh_0$ 与 $rubl_0$ 匹配。
求解公式即为 $\sum \limits {i=1}^{k-1} rubh_i \times rubl{k-i} + rubh_0 \times rubl_0$，时间复杂度 $\mathcal{O}(q + k)$。
代码
#include<bits/stdc++.h>
using namespace std;
namespace fast_IO
{
/*
快读快写
*/
};
using namespace fast_IO;
int n,m,q,k,hang[200010],lie[200010],rubh[500010],rubl[500010];
inline void delh(int x)
{
if(x==k-1) rubh[x]--,rubh[0]++;
else rubh[x]--,rubh[x+1]++;
}
inline void dell(int x)
{
if(x==k-1) rubl[x]--,rubl[0]++;
else rubl[x]--,rubl[x+1]++;
}
long long ans;
int main()
{
read(n),read(m),read(q),read(k),rubh[0]=n,rubl[0]=m;
for(int i=1,op,x;i<=q;i++)
{
read(op),read(x);
if(op==1) hang[x]++,delh((hang[x]-1)%k);
else lie[x]++,dell((lie[x]-1)%k);
}
ans+=1ll*rubh[0]*rubl[0];
for(int i=1;i<k;i++) ans+=1ll*rubh[i]*rubl[k-i];
cout<<1ll*n*m-ans;
return 0;
}
