ABC346E 题解

KSCD_ · 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;
}