首页 > 代码库 > BZOJ3132 上帝造题的七分钟
BZOJ3132 上帝造题的七分钟
二维树状数组。。。
就是要记一堆东西,不想详细描述了233
我去。。。多打了个分号调了1h。。。蒟蒻给跪了。。。
快嘲笑蒟蒻!!!
1 /************************************************************** 2 Problem: 3132 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:16372 ms 7 Memory:66796 kb 8 ****************************************************************/ 9 10 #include <cstdio>11 12 #define lowbit(p) p & -p13 using namespace std;14 const int N = 2055;15 16 int n, m, del;17 struct BIT {18 int t[N][N];19 20 inline void add(int x, int y, int del) {21 int Y;22 for (; x <= n; x += lowbit(x))23 for (Y = y; Y <= m; Y += lowbit(Y))24 t[x][Y] += del;25 }26 27 inline int sum(int x, int y) {28 int Y, res = 0;29 for (; x; x -= lowbit(x))30 for (Y = y; Y; Y -= lowbit(Y))31 res += t[x][Y];32 return res;33 }34 } b1, b2, b3, b4;35 36 inline void update(int x, int y) {37 if (!x || !y) return;38 b1.add(x, y, x * y * del);39 b2.add(x, 1, x * del), b2.add(x, y, -x * del);40 b3.add(1, y, y * del), b3.add(x, y, -y * del);41 b4.add(1, 1, del), b4.add(x, y, del);42 b4.add(x, 1, -del), b4.add(1, y, -del);43 }44 45 inline int query(int x, int y) {46 return b1.sum(x, y) + b2.sum(x, y) * y + b3.sum(x, y) * x + b4.sum(x, y) * x * y;47 }48 49 int main() {50 char oper;51 int x1, x2, y1, y2;52 scanf(" %*c%d%d\n", &n, &m);53 while (scanf(" %c%d%d%d%d", &oper, &x1, &y1, &x2, &y2) != EOF) {54 if (oper == ‘L‘) {55 scanf("%d", &del);56 update(x2, y2), update(x1 - 1, y1 - 1);57 del = -del;58 update(x2, y1 - 1), update(x1 - 1, y2);59 } else60 printf("%d\n", query(x2, y2) + query(x1 - 1, y1 - 1) - query(x2, y1 - 1) - query(x1 - 1, y2));61 }62 return 0;63 }
BZOJ3132 上帝造题的七分钟
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。