欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

HDU - 6514 Monitor(二维差分)

程序员文章站 2022-07-12 17:38:44
...

题意

给定一个\(n×m\)的矩阵。(\(n×m <= 1e7\))。
\(p\)次操作,每次可以在这个矩阵中覆盖一个矩形。
\(q\)次询问,每次问一个矩形区域中,是否所有的点都被覆盖。

解析

修改的时候用二维差分,判断的时候用二维前缀和。
增加矩形\((x1, y1),(x2, y2)\)时:

dis[id(x1, y1)]++;
dis[id(x1, y2+1)]--;
dis[id(x2+1, y1)]--;
dis[id(x2+1, y2+1)]++;

求矩形\((x1,y1),(x2,y2)\)的区间和时:

sum[id(x2, y2)] - (sum[id(x1-1, y2)] + sum[id(x2, y1-1)] - sum[id(x1-1, y1-1)])

代码

#include <bits/stdc++.h>

#define FOPI freopen("in.txt", "r", stdin")
#define FOPO freopen("out.txt", "w", stdout")
#define FOR(i,x,y) for (int i = x; i <= y; i++)
#define ROF(i,x,y) for (int i = x; i >= y; i--)

using namespace std;
typedef long long LL;
const int maxn = 2e7 + 100;

int dis[maxn], sum[maxn];
int n, m, p, q;
int x1, y1, x2, y2;

int id(int i, int j)
{
    if (i == 0 || j == 0 || i > n || j > m) return 0;
    return (i-1)*m + j;
}

int main()
{
    while(~scanf("%d%d", &n, &m))
    {
        FOR(i, 1, n*m) dis[i] = 0;

        scanf("%d", &p);
        FOR(i, 1, p)
        {
            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            if (id(x1, y1)) dis[id(x1, y1)]++;
            if (id(x1, y2+1)) dis[id(x1, y2+1)]--;
            if (id(x2+1, y1)) dis[id(x2+1, y1)]--;
            if (id(x2+1, y2+1)) dis[id(x2+1, y2+1)]++;
        }
        
        FOR(i, 1, n) FOR(j, 1, m)
            sum[id(i,j)] = sum[id(i-1,j)] + sum[id(i,j-1)] - sum[id(i-1,j-1)] + dis[id(i,j)];

        FOR(i, 1, n) FOR(j, 1, m) sum[id(i,j)] = sum[id(i,j)] > 0;

        FOR(i, 1, n) FOR(j, 1, m)
            sum[id(i,j)] = sum[id(i-1,j)] + sum[id(i,j-1)] - sum[id(i-1,j-1)] + sum[id(i,j)];

        scanf("%d", &q);
        FOR(i, 1, q)
        {
            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            if (sum[id(x2, y2)] - (sum[id(x1-1, y2)] + sum[id(x2, y1-1)] - sum[id(x1-1, y1-1)]) == (x2-x1+1) * (y2-y1+1)) 
            printf("YES\n");
            else printf("NO\n");
        }
    }
}