C++(g++ 7.5.0) 解法, 执行用时: 489ms, 内存消耗: 27376K, 提交时间: 2023-05-23 16:00:12

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+5;
int a[N][N];
int v[N*N][5];
int n,m;
int ans;
int s[N*N];
void modify(int x){
	a[v[x][1]][v[x][2]]++;
	a[v[x][1]][v[x][4]+1]--;
	a[v[x][3]+1][v[x][2]]--;
	a[v[x][3]+1][v[x][4]+1]++;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			int x;cin>>x;
			s[x]++;
			if(s[x]==1){
				v[x][1]=i;
				v[x][2]=j;
				v[x][3]=i;
				v[x][4]=j;
			}if(s[x]>=2){
				v[x][1]=min(v[x][1],i);
				v[x][2]=min(v[x][2],j);
				v[x][3]=max(v[x][3],i);
				v[x][4]=max(v[x][4],j);
			}
		}
	}for(int i=1;i<=1e6;i++){
		if(s[i]>=2){
			modify(i);
		}
	}for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
			if(!a[i][j]) ans++;
		}
	}cout<<ans;
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 451ms, 内存消耗: 19692K, 提交时间: 2022-09-20 22:32:07

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10,M=1e6+10;
struct node {
	int a,b,c,d;
} t[M];
int n,m,p,ans;
int s[N][N];
signed main() {
	cin>>n>>m;
	for(int i = 1; i<=n; i++)
		for(int j = 1; j<=m; j++) {
			int x; cin>>x;
			if(!t[x].a or i>t[x].a) t[x].a=i;
			if(!t[x].b or j>t[x].b) t[x].b=j;
			if(!t[x].c or i<t[x].c) t[x].c=i;
			if(!t[x].d or j<t[x].d) t[x].d=j;
			p=max(p,x);
		}
	for(int i = 1; i<=p; i++) {
		if(!t[i].a or (t[i].a==t[i].c and t[i].b==t[i].d)) continue;
		int a=t[i].a,b=t[i].b,c=t[i].c,d=t[i].d;
		s[c][d]+=1,s[a+1][b+1]+=1,s[a+1][d]-=1,s[c][b+1]-=1;
	}
	for(int i = 1; i<=n; i++)
		for(int j = 1; j<=m; j++) {
			s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
			if(!s[i][j]) ans++;
		}
	cout<<ans;
	return 0;
}