首页 > 代码库 > bzoj3132
bzoj3132
二维树状数组
树状数组什么的只支持修改单个数值,但是这道题要我们更新一个区域
盗图
就是这样,然后维护四个bit就行了
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 2049; int n, m; char s[10]; struct bit { int tree[N][N]; int lowbit(int i) { return i & -i; } void update(int x, int y, ll delta) { for(int i = x; i <= n; i += lowbit(i)) for(int j = y; j <= m; j += lowbit(j)) tree[i][j] += delta; } int query(int x, int y) { ll ret = 0; for(int i = x; i; i -= lowbit(i)) for(int j = y; j; j -= lowbit(j)) ret += tree[i][j]; return ret; } } A, B, C, D; void add(int a, int b, int c, int d, int delta) { A.update(c + 1, d + 1, delta); A.update(a, b, delta); A.update(a, d + 1, -delta); A.update(c + 1, b, -delta); B.update(c + 1, d + 1, (c + 1) * delta); B.update(a, b, a * delta); B.update(a, d + 1, -a * delta); B.update(c + 1, b, -(c + 1) * delta); C.update(c + 1, d + 1, (d + 1) * delta); C.update(a, b, b * delta); C.update(a, d + 1, -(d + 1) * delta); C.update(c + 1, b, -b * delta); D.update(c + 1, d + 1, (c + 1) * (d + 1) * delta); D.update(a, b, a * b * delta); D.update(a, d + 1, -a * (d + 1) * delta); D.update(c + 1, b, -(c + 1) * b * delta); } int getans(int a, int b) { return (a + 1) * (b + 1) * A.query(a, b) - (a + 1) * C.query(a, b) - (b + 1) * B.query(a, b) + D.query(a, b); } int getans(int a, int b, int c, int d) { return getans(c, d) - getans(a - 1, d) - getans(c, b - 1) + getans(a - 1, b - 1); } int main() { scanf(" X %d %d", &n, &m); while(scanf("%s", s) != EOF) { int a, b, c, d, delta; if(s[0] == ‘L‘) { scanf("%d%d%d%d%d", &a, &b, &c, &d, &delta); add(a, b, c, d, delta); } if(s[0] == ‘k‘) { scanf("%d%d%d%d", &a, &b, &c, &d); printf("%d\n", getans(a, b, c, d)); } } return 0; }
bzoj3132
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。