牛牛的方格图 (二维差分）

牛牛：“你喜欢玩数独吗？”。

牛牛有一个

的方格图，每个格子都有自己的颜色，第 行第 列格子上的颜色记为 。

对于任意两个不同位置的颜色相同的点，我们认为其覆盖了一个以它们为对角线上顶点的矩形中的所有点。

现在牛牛想知道这张方格图中有多少个顶点尚未被覆盖。

 题解：

根据你遍历的顺序差分一下就行了。

#include#include#include#include#includeusing namespace std;int n,m,d[1005][1005];vector<pair > v[1000005];int main(){    scanf("%d%d",&n,&m);    int x;    for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){     scanf("%d",&x);     v[x].push_back({i,j}); }    }    for(int i=1;i<=1000000;i++){ if(v[i].size()<=1) continue; int mxx=0,mnx=1e9,mxy=0,mny=1e9; for(auto vv:v[i]){     mxx=max(mxx,vv.first);     mnx=min(mnx,vv.first);     mxy=max(mxy,vv.second);     mny=min(mny,vv.second); } // printf("%d %d %d %d\n",mnx,mxx,mny,mxy); d[mnx][mny]+=1; d[mnx][mxy+1]-=1; d[mxx+1][mxy+1]+=1; d[mxx+1][mny]-=1;    }    int ans=0;    for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){     d[i][j]+=d[i-1][j]+d[i][j-1]-d[i-1][j-1];     if(!d[i][j]) ++ans;     // printf("%3d",d[i][j]); } // puts("");    }    printf("%d\n",ans);    return 0;}