[牛客月赛47] E牛牛的方格图 二维差分矩阵

前言

传送门 :

题意

给定一个 n ∗ m n*m n∗m的数组,对于 a [ i , j ] a[i,j] a[i,j]表示当前 [ i , j ] [i,j] [i,j]的颜色

两个相同颜色的点,可以使得将其 [ x 1 , y 1 , x 2 , y 2 ] [x1,y1,x2,y2] [x1,y1,x2,y2]的范围内所有的颜色都覆盖掉

询问有多少个点没有被覆盖

思路

首先做这题没有什么思路,感觉点很多

但是其实画了一个图之后会发现,当前颜色所能影响的点为 m a x [ x 1 , y 1 ] m i n [ x 2 , y 2 ] max[x1,y1]min[x2,y2] max[x1,y1]min[x2,y2]

即将所有点进行颜色分组,他能影响的范围也就是 最 大 的 x y 和 最 小 的 x y 最大的xy和最小的xy 最大的xy和最小的xy

对于一种比较难想的下图解释,如图显然就算当前图形有缺口,我们也可也使用另外两个节点补上

因此我们需要将所有点进行颜色分组并且记录 x , y x,y x,y,然后求得所有节点的左上角和右下角

因为是求覆盖问题,我们可以考虑使用二维差分矩阵

然后求一遍前缀和即可

Code

const int N = 1e6+10 , INF  =  0x3f3f3f3f3f;
int a[N][4];
int n,m;
int sum[1010][1010];

void solve(){
	cin>>n>>m;
	for(int i = 1;i