首先我们需要特判只涂了一种颜色的情况:

(1)k=1,此时答案就是1；(2)k>1,涂的这种颜色肯定不能是第一个，答案是k-1;

对于其他正常情况，我们对于每个颜色找到一个最小的矩形（这个矩形内包含这种颜色出现的所有位置），用二维差分处理（sum数组），最后统计。如果某位置sum>1，说明这个位置被涂了不止一次，这种颜色就不可能是第一个涂的，打标记。最后统计没有打标记的颜色数量就是答案。

1 #include
2 #define int long long
3 using namespace std;
4 int read(){
5 int x=0,f=1;char c=getchar();
6 while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
7 while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); 8 return x*f; 9 } 10 const int N=5e5+10; 11 const int INF=0x3f3f3f3f; 12 int n,m,k,tot,col[N],sum[N],ans; 13 struct node{ 14 int lx,rx,ly,ry,tag,fag; 15 }a[N];//存的是每个颜色的信息 16 int id(int x,int y){ 17 return (x-1)*m+y; 18 } 19 20 signed main(){ 21 //freopen("paint.in","r",stdin); 22 //freopen("paint.out","w",stdout); 23 n=read(),m=read(),k=read(); 24 for(int i=0;i<=k;i++) a[i].lx=a[i].ly=INF; 25 for(int i=1;i<=n;i++) 26 for(int j=1;j<=m;j++){ 27 int x=read(); 28 if(!a[x].tag) a[x].tag=1,tot++;//tot用来统计最后图中颜色个数 29 a[x].lx=min(a[x].lx,i),a[x].ly=min(a[x].ly,j); 30 a[x].rx=max(a[x].rx,i),a[x].ry=max(a[x].ry,j);//找边界 31 col[id(i,j)]=x; 32 } 33 if(tot==1) {if(k==1) puts("1");else cout<1) a[col[id(i,j)]].fag=1;//该位置不可能是第一个涂的
43 for(int i=1;i<=k;i++) if(!a[i].fag) ans++;
44 printf("%lld",ans);
45 }
46
47