题目描述

这道题要求我们在一个二维矩阵中找出第一次可能使用的颜色个数，即被破坏或完整的不同数字矩形个数，也即 $n^2-ans$，$ans$ 为破坏其他矩形的数字个数。

解题思路

考虑第三种解释：用 $n^2-ans$。对于矩形的重复覆盖，我们有两个个较为常用的算法：二维前缀和 和 二维差分。我们只需要将每一个数字出现过的左上角和右下角记录下来进行差分，再从头扫一遍二维前缀和即可求出每个位置被覆盖的次数，那么如果此时该位置的次数大于 $1$ 且该位置数字是第一次出现，即可使 $ans$ 加上 $1$。最后输出 $n^2-ans$ 即可。记得特判只有一种数字出现的情况，直接输出 $n^2-1$ 即可，不然会 WA 第二个测试点。

完结撒花~

献上蒟蒻的 AC 代码：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1000010;

int n,k;
int a[N];
bool vis[N],v[N];
int d[N],maxx[N],maxy[N],minx[N],miny[N];
int ans,cnt,st[N];

int main()
{
	scanf("%d",&n);k=n*n;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			scanf("%d",&a[(i-1)*n+j]);
			if(!a[(i-1)*n+j]) continue;
			if(!vis[a[(i-1)*n+j]])
			{
				cnt++;vis[a[(i-1)*n+j]]=true;
				minx[a[(i-1)*n+j]]=n+1,miny[a[(i-1)*n+j]]=n+1;
				st[cnt]=a[(i-1)*n+j];
			}
			maxx[a[(i-1)*n+j]]=max(maxx[a[(i-1)*n+j]],i);
			maxy[a[(i-1)*n+j]]=max(maxy[a[(i-1)*n+j]],j);
			minx[a[(i-1)*n+j]]=min(minx[a[(i-1)*n+j]],i);
			miny[a[(i-1)*n+j]]=min(miny[a[(i-1)*n+j]],j);
		}
	}
	
	if(cnt==1)
	{
		printf("%d",k-1);
		return 0;
	}
	
	for(int i=1;i<=cnt;i++)
	{
		d[(minx[st[i]]-1)*n+miny[st[i]]]++;
		d[maxx[st[i]]*n+miny[st[i]]]--;
		d[(minx[st[i]]-1)*n+maxy[st[i]]+1]--;
		d[maxx[st[i]]*n+maxy[st[i]]+1]++;
	}
	
	for(int i=1;i<=n*n;i++)
	{
		d[i]+=d[i-1]+d[i-n]-d[i-n-1];
		if(d[i]>1&&!v[a[i]])
		{
			v[a[i]]=true;
			ans++;
		}
	}
	printf("%d",k-ans);
	return 0;
}

细节处理

1.将二维序号降为一维以防止数据过大。不过本题不需要，如果遇到的是 $n \times m$ 范围时则需要该处理防止爆仓。