本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-03-23 23:33:04

题意

有一个 $H$ 行 $W$ 列网格，初始均为颜色 $0$。$M$ 次操作，每次把一整行或一整列涂成一种颜色，求最后的颜色种数和每种颜色的格子数。

思路

暴力修改查找复杂度过高，无法通过本题。

我们发现每次操作都会覆盖之前的操作，所以考虑倒序处理，这样每次就能直接确定下若干格的颜色，之后不再考虑这些格。

那么若涂某一行，则以后再涂这行就不再产生影响，再涂列时都不会再涂这行的那一格。涂某一列造成的影响也一样。

如此处理，由于初始为颜色 $0$，最后把没涂过的格子涂成颜色 $0$ 即可。

具体看代码实现吧。

代码

#include<iostream>
#define int long long
using namespace std;
const int N=2e5+10;
int read()
{
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){ if(ch=='-') w=-1; ch=getchar();}
    while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar();}
    return s*w;
}
struct nod
{
	int t,x,id;
}a[N];
bool hang[N],lie[N];\/\/标记某一行\/列是否整体被涂过 
int h,w,m,sum[N],aa[N],ab[N],cnt; 
signed main()
{
	h=read(),w=read(),m=read();
	int th=h,tw=w;\/\/剩余可涂的行\/列数 
	for(int i=1;i<=m;i++) a[i].t=read(),a[i].id=read(),a[i].x=read();
	for(int i=m;i>=1;i--)\/\/记录操作并倒序处理 
	{
		if(a[i].t==1)\/\/涂行 
		{
			if(hang[a[i].id]) continue;\/\/涂过就跳过
			hang[a[i].id]=1,sum[a[i].x]+=tw;\/\/标记并更新答案 
			th--;\/\/之后涂列时少涂一格 
		}
		else\/\/涂列同上 
		{
			if(lie[a[i].id]) continue;
			lie[a[i].id]=1,sum[a[i].x]+=th;
			tw--;
		}
	}
	sum[0]=h*w;
	for(int i=1;i<=2e5;i++) sum[0]-=sum[i];\/\/从总数中减掉非零的格子数 
	for(int i=0;i<=2e5;i++) if(sum[i]) 
		aa[++cnt]=i,ab[cnt]=sum[i];\/\/记录答案 
	cout<<cnt<<"\n";
	for(int i=1;i<=cnt;i++) cout<<aa[i]<<' '<<ab[i]<<"\n";
	return 0;
}