题意
给定一个\(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");
}
}
}