首页 > 代码库 > 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 }
View Code

 

BZOJ3132 上帝造题的七分钟