Monitor HDU - 6514（二维差分，二维前缀和）

本文主要是介绍Monitor HDU - 6514（二维差分，二维前缀和），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://vjudge.net/problem/HDU-6514#

二维差分：

// x1，y1是左上角，x2，y2是右下角
sum[x1][y1]+=d;
sum[x1][y2+1]-=d;
sum[x2+1][y1]-=d;
sum[x2+1][y2+1]+=d;

求前缀和：

 for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++)sum[i][j] = sum[i][j] + sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1];

求一个区间的和：

ans = sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];

#include <bits/stdc++.h>using namespace std;void modify(int x1, int y1, int x2, int y2, int d, vector<vector<int> > & sum)
{   sum[x1][y1]+=d;sum[x1][y2+1]-=d;sum[x2+1][y1]-=d;sum[x2+1][y2+1]+=d;
}void update(int n, int m, vector<vector<int> > & sum) {for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++)sum[i][j] = sum[i][j] + sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1];for(int i = 1; i <= n; i++) {for(int j = 1; j <= m; j++) {if(sum[i][j] > 0) {sum[i][j] = 1;}}}for(int i = 1; i <= n; i++) {for(int j = 1; j <= m; j++) {sum[i][j] = sum[i][j] + sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1];}}
}int main()
{// freopen("i.txt", "r", stdin);int n, m;while(~scanf("%d%d", &n, &m)) {vector<vector<int> > sum(n + 5, vector<int>(m + 5, 0));int T;scanf("%d", &T);while(T--) {int x1, y1, x2, y2;scanf("%d%d%d%d", &x1, &y1, &x2, &y2);modify(x1, y1, x2, y2, 1, sum);}update(n, m,sum);scanf("%d", &T);while(T--){int x1, y1, x2, y2;scanf("%d%d%d%d", &x1, &y1, &x2, &y2);if(sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1] == (x2-x1+1) * (y2-y1+1)) {printf("YES\n");}else printf("NO\n");}  }return 0;
}

这篇关于Monitor HDU - 6514（二维差分，二维前缀和）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---