Modern Art(差分)

Modern Art

思路

反向考虑不可能的情况，用$n^2$减即为答案，即某个位置被覆盖过一次以上的颜色，且每种颜色只有一次贡献，注意特判一下$n>1,color_{cnt}=1$的情况，因为这种情况

也不可能是第一次涂的颜色，即差分+前缀和即可。

时间复杂度：$O(n^2)$

---

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
int a[N][N];
int dif[N][N];
int b[N*N][4],n,vis[N*N];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n*n;i++)
        b[i][0]=b[i][1]=inf,b[i][2]=b[i][3]=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            scanf("%d",&a[i][j]);
            if(a[i][j]){
                int c=a[i][j];
                b[c][0]=min(b[c][0],i);
                b[c][1]=min(b[c][1],j);
                b[c][2]=max(b[c][2],i);
                b[c][3]=max(b[c][3],j);
            }
        }
    int cnt=0;
    for(int i=1;i<=n*n;i++){
        if(b[i][0]==inf) continue;
        cnt++;
        dif[b[i][0]][b[i][1]]++;
        dif[b[i][2]+1][b[i][3]+1]++;
        dif[b[i][0]][b[i][3]+1]--;
        dif[b[i][2]+1][b[i][1]]--;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            dif[i][j]=dif[i][j]-dif[i-1][j-1]+dif[i-1][j]+dif[i][j-1];
    int ans=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(dif[i][j]>1&&a[i][j]&&!vis[a[i][j]]){
                ans++,vis[a[i][j]]=1;
            }
    printf("%d\n",n*n-ans-(cnt==1&&n>1));
    return 0;
}