本文主要是介绍【数据结构 二维树状数组】luogu_ 4514 上帝造题的七分钟,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题意
维护矩阵区间和,区间修改操作。
思路
二维树状数组。
先挖坑,这里贴篇blog
代码
#include <cstdio>int n, m, a, b, c, d, delta;
char op;
int t[4][2100][2100];inline int lowbit(int x) {return x & -x;
}void add(int x, int y, int val) {for (int i = x; i <= n; i += lowbit(i))for (int j = y; j <= m; j += lowbit(j)) {t[0][i][j] += val;t[1][i][j] += val * x;t[2][i][j] += val * y;t[3][i][j] += val * x * y;}
}int query(int op, int x, int y) {int res = 0;for (int i = x; i >= 1; i -= lowbit(i))for (int j = y; j >= 1; j -= lowbit(j))res += t[op][i][j];return res;
}int ask(int x, int y) {return query(0, x, y) * (x * y + x + y + 1) - query(1, x, y) * (y + 1) - query(2, x, y) * (x + 1) + query(3, x, y);
}int main() {scanf("X %d %d", &n, &m);while (scanf("%s", &op) != EOF) {scanf("%d %d %d %d", &a, &b, &c, &d);if (op == 'L') {scanf("%d", &delta);add(a, b, delta);add(a, d + 1, -delta);add(c + 1, b, -delta);add(c + 1, d + 1, delta);} else printf("%d\n", ask(c, d) - ask(a - 1, d) - ask(c, b - 1) + ask(a - 1, b - 1));}
}
这篇关于【数据结构 二维树状数组】luogu_ 4514 上帝造题的七分钟的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!