HDU 6514. 二维前缀和与差分
原题链接
简单
作者:
史一帆
,
2021-04-27 19:37:38
,
所有人可见
,
阅读 176
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
typedef vector<int> VI;
vector<VI> v;
int n, m, q;
int min(int a, int b)
{
return a < b ? a : b;
}
int main()
{
while (~scanf("%d%d", &n, &m))
{
v.resize(n + 5);
for (int i = 0; i <= n + 1; i ++ )
{
v[i].resize(m + 5);
for (int j = 0; j <= m + 1; j ++ )
v[i][j] = 0;
}
scanf("%d", &q);
while (q -- )
{
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
v[x1][y1] ++ ;
v[x1][y2 + 1] -- ;
v[x2 + 1][y1] -- ;
v[x2 + 1][y2 + 1] ++ ;
}
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
v[i][j] += v[i - 1][j] + v[i][j - 1] - v[i - 1][j - 1];
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
v[i][j] = min(1, v[i][j]);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
v[i][j] += v[i - 1][j] + v[i][j - 1] - v[i - 1][j - 1];
scanf("%d", &q);
while (q -- )
{
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
int ans = v[x2][y2] - v[x2][y1 - 1] - v[x1 - 1][y2] + v[x1 - 1][y1 - 1];
if (ans == (x2 - x1 + 1) * (y2 - y1 + 1)) printf("YES\n");
else printf("NO\n");
}
}
return 0;
}