Codeforces 707 E. Garlands (二维树状数组)

题目链接：http://codeforces.com/problemset/problem/707/E

给你nxm的网格，有k条链，每条链上有len个节点，每个节点有一个值。

有q个操作，操作ask问你一个子矩阵的和是多少，操作switch将第i条链上的值0变原来的数or原来的数变0。

比较明显的二维数组数组暴力，注意的是ask操作不会超过2000，所以在switch操作的时候不能进行update操作，否则会超时。所以你在ask操作的时候update就会省时。

复杂度大概是2000*2000*log2(2000)*log2*(2000)，cf上3s妥妥过。

 //#pragma comment(linker, "/STACK:102400000, 102400000")

 #include <algorithm>

 #include <iostream>

 #include <cstdlib>

 #include <cstring>

 #include <cstdio>

 #include <vector>

 #include <cmath>

 #include <ctime>

 #include <list>

 #include <set>

 #include <map>

 using namespace std;

 typedef long long LL;

 typedef pair <int, int> P;

 const int N = 2e3 + ;

 int n, m;

 LL bit[N][N];

 struct data {

     int x[N], y[N], w[N], len;

 }a[N];

 bool change[N];

 int flag[N];

 void update(int x, int y, LL val) {

     for(int i = x; i <= n; i += (i&-i)) {

         for(int j = y; j <= m; j += (j&-j)) {

             bit[i][j] += val;

         }

     }

 }

 LL sum(int x, int y) {

     LL s = ;

     for(int i = x; i >= ; i -= (i&-i)) {

         for(int j = y; j >= ; j -= (j&-j)) {

             s += bit[i][j];

         }

     }

     return s;

 }

 int main()

 {

     int k, q;

     scanf("%d %d %d", &n, &m, &k);

     for(int i = ; i <= k; ++i) {

         scanf("%d", &a[i].len);

         for(int j = ; j <= a[i].len; ++j) {

             scanf("%d %d %d", &a[i].x[j], &a[i].y[j], &a[i].w[j]);

             update(a[i].x[j], a[i].y[j], (LL)a[i].w[j]);

         }

     }

     scanf("%d", &q);

     char query[];

     int x1, y1, x2, y2, c;

     for(int i = ; i <= q; ++i) {

         scanf("%s", query);

         if(query[] == 'A') {

             scanf("%d %d %d %d", &x1, &y1, &x2, &y2);

             for(int id = ; id <= k; ++id) {

                 if(change[id]) {

                     if(flag[id] % ) {

                         for(int j = ; j <= a[id].len; ++j) {

                             update(a[id].x[j], a[id].y[j], (LL)a[id].w[j]);

                         }

                     } else {

                         for(int j = ; j <= a[id].len; ++j) {

                             update(a[id].x[j], a[id].y[j], (LL)-a[id].w[j]);

                         }

                     }

                     change[id] = change[id] ? false: true;

                     ++flag[id];

                 }

             }

             printf("%lld\n", sum(x2, y2) - sum(x2, y1 - ) - sum(x1 - , y2) + sum(x1 - , y1 - ));

         } else {

             scanf("%d", &c);

             change[c] = change[c] ? false: true;

         }

     }

     return ;

 }

巴特西

Codeforces 707 E. Garlands (二维树状数组)

最新文章

热门文章