牛牛的方格图【牛客tracker 每日一题】

牛牛的方格图时间限制1秒 空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述牛牛“你喜欢玩数独吗”。牛牛有一个n ⋅ m n⋅mn⋅m的方格图每个格子都有自己的颜色第i ii行第j jj列格子上的颜色记为c o l ( i , j ) col(i,j)col(i,j)。对于任意两个不同位置的颜色相同的点我们认为其覆盖了一个以它们为对角线上顶点的矩形中的所有点。严格来说一个点P ( i p , j p ) P(i_p,j_p)P(ip​,jp​)被覆盖当且仅当存在两个点A ( i a , j a ) A(i_a,j_a)A(ia​,ja​)和B ( i b , j b ) B(i_b,j_b)B(ib​,jb​)使得以下四个条件都成立1 c o l ( i a , j a ) c o l ( i b , j b ) 1col(i_a,j_a)col(i_b,j_b)1col(ia​,ja​)col(ib​,jb​)2 i a ≠ i b ∣ ∣ j a ≠ j b 2i_a≠i_b∣∣j_a≠j_b2ia​ib​∣∣ja​jb​3 m i n ( i a , i b ) ≤ i p ≤ m a x ( i a , i b ) 3min(i_a,i_b)≤i_p≤max(i_a,i_b)3min(ia​,ib​)≤ip​≤max(ia​,ib​)4 m i n ( j a , j b ) ≤ j p ≤ m a x ( j a , j b ) 4min(j_a,j_b)≤j_p≤max(j_a,j_b)4min(ja​,jb​)≤jp​≤max(ja​,jb​)现在牛牛想知道这张方格图中有多少个顶点尚未被覆盖。输入描述第一行输入两个数n , m n,mn,m代表方格图的行数和列数。接下来n nn行每行m mm个数描述了方格图中每个格子上的颜色。1 ≤ n , m ≤ 10 3 1≤n,m≤10^31≤n,m≤1031 ≤ c o j ( i , j ) ≤ 10 6 1≤coj(i,j)≤10^61≤coj(i,j)≤106输出描述输出一行一个整数代表答案。示例1输入3 4 1 3 3 4 2 3 1 4 6 3 3 4输出1说明6所在方格未被覆盖。解题思路本题的核心是通过几何性质推导 二维差分将复杂的点对覆盖问题简化为矩形并集计数在O ( n m ) O(nm)O(nm)时间内高效求解。1. 核心性质同色覆盖区域等价于边界矩形对于任意一种颜色所有同色点对生成的矩形的并集恰好等于该颜色所有点的最小行、最大行、最小列、最大列构成的完整轴对齐矩形。上界任意两个同色点的矩形都必然包含在这个边界矩形之内因此并集不会超出该范围。下界边界矩形内的任意一点总能找到两个同色点使得该点落在它们的对角矩形中行被两点行范围包含列被两点列范围包含因此整个矩形都被覆盖。由此可得结论若某颜色仅出现1次单点不存在点对不覆盖任何格子。若某颜色出现≥2次其覆盖区域就是[minx, maxx] × [miny, maxy]的完整矩形。2. 问题转化矩形并集计数原问题转化为给定若干轴对齐矩形求网格中未被任何矩形覆盖的格子数量。由于网格规模仅为1000 × 1000 1000 \times 10001000×1000使用二维差分数组即可高效处理批量矩形覆盖每个矩形覆盖操作可通过差分数组的4个端点修改完成时间复杂度O ( 1 ) O(1)O(1)。最终通过二维前缀和还原每个格子的覆盖次数统计覆盖次数为0的格子数即为答案。3. 算法执行步骤统计颜色边界遍历整个网格对每种颜色记录最小行号minx、最大行号maxx、最小列号miny、最大列号maxy。差分标记覆盖遍历所有颜色跳过未出现和仅单点的颜色对有效颜色用二维差分数组给其边界矩形区域 1。前缀和统计结果对差分数组计算二维前缀和得到每个格子的覆盖次数统计覆盖次数为0的格子总数即为未被覆盖的答案。算法总时间复杂度为O ( n m ) O(nm)O(nm)完全适配题目数据规模。总结核心逻辑通过几何性质将点对覆盖简化为边界矩形覆盖利用二维差分高效处理矩形并集最终统计未覆盖格子数。关键操作颜色边界统计、二维差分区间更新、前缀和还原与计数。效率保障线性时间复杂度百万级网格运算量1秒内可轻松完成。代码简要说明数组定义二维数组a存储原始方格图颜色vis作为二维差分数组。四个一维数组minx/maxx/miny/maxy记录每种颜色的边界坐标长度适配颜色最大值1e6。边界统计双重循环读入每个格子的颜色同步更新对应颜色的四个边界值初始min设为极大值、max设为0。差分更新遍历1到1e6的所有颜色过滤未出现maxx为0和单点行、列范围均为1的颜色对有效颜色执行差分矩形加1操作。前缀和与计数按行优先计算二维前缀和每计算完一个格子就判断是否为0若是则答案计数加1。结果输出输出未被覆盖的格子总数。输入优化关闭流同步加速输入适配千级网格的读取效率。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n,m;cinnm;vectorvectorlla(n1,vectorll(m1));vectorvectorllvis(n2,vectorll(m2,0));vectorllminx(1000010,INF),maxx(1000010,0),miny(1000010,INF),maxy(1000010,0);for(ll i1;in;i)for(ll j1;jm;j){cina[i][j];ll va[i][j];if(imaxx[v])maxx[v]i;if(iminx[v])minx[v]i;if(jmaxy[v])maxy[v]j;if(jminy[v])miny[v]j;}for(ll i1;i1000000;i){if(maxx[i]0)continue;if(maxx[i]minx[i]miny[i]maxy[i])continue;vis[minx[i]][miny[i]];vis[minx[i]][maxy[i]1]--;vis[maxx[i]1][miny[i]]--;vis[maxx[i]1][maxy[i]1];}ll ans0;for(ll i1;in;i)for(ll j1;jm;j){vis[i][j]vis[i-1][j]vis[i][j-1]-vis[i-1][j-1];if(vis[i][j]0)ans;}coutansendl;return0;}