【每日一题】Modern Art

题意：

给定一个nn的矩阵，一开始上面没有任何颜色(也就是都为0)。之后进行nn次染色，每次选择一个[1,nn]的颜色，且每种颜色都只会被选择一次。然后在矩阵上选择任意大小和任意位置的子矩阵进行染色，规定后面的染色会覆盖前面的染色。在给出矩阵最终的染色情况下，问第一次染色选择的颜色种类可能有多少种。

分析：

如果(x,y)处染色的次数大于等于2，那么(x,y)处的颜色肯定不能作为第一次染色选择的颜色。因此我们用一个矩阵S，S[i][j]表示(i,j)处的染色次数，初值均为0。然后对每种颜色记录他的左上角点和右下角点，使得这两点确定的矩阵内所有元素加一，在这里我们可以使用二维差分数组进行优化。之后判断每个位置的S[i][j]，若S[i][j]大于等于2，则置(i,j)处的颜色的标记数组为0，表示该种颜色无法用于第一次染色。之后用ans统计一遍标记数组从1~nn中1的个数即可。
写完以上思想的代码快速交了一发，结果过了90%，肯定是还有什么特殊情况没有考虑。我们考虑这种情况：假如给出的矩阵里面只有一种颜色，那么通过以上思想求出的答案是nn，但是答案显然是nn-1才对。因此我们特判一下这种情况，就能顺利通过此题了。

代码：

#include<bits/stdc++.h>
using namespace std;

int a[1005][1005],S[1005][1005]={0};
int xmi[1000005],xmx[1000005],ymi[1000005],ymx[1000005];
bool V[1000005];
int main()
{
    int i,j,n,id,ans=0;
    scanf("%d",&n);
    for(i=1;i<=n*n;i++)xmi[i]=ymi[i]=1e9,xmx[i]=ymx[i]=0,V[i]=1;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        {
            scanf("%d",&a[i][j]),id=a[i][j];
            xmi[id]=min(xmi[id],i);
            xmx[id]=max(xmx[id],i);
            ymi[id]=min(ymi[id],j);
            ymx[id]=max(ymx[id],j);
        }
    for(i=1;i<=n*n;i++)
    {
        if(!xmx[i])continue;
        ans++;
        S[xmi[i]][ymi[i]]++;
        S[xmi[i]][ymx[i]+1]--;
        S[xmx[i]+1][ymi[i]]--;
        S[xmx[i]+1][ymx[i]+1]++;
    }
    if(ans==1){printf("%d\n",n*n-1);return 0;}
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        {
            S[i][j]+=S[i-1][j]+S[i][j-1]-S[i-1][j-1];
            if(S[i][j]>=2)V[a[i][j]]=0;
        }
    for(ans=0,i=1;i<=n*n;i++)ans+=V[i];
    printf("%d\n",ans);
    return 0;
}