【题目链接】:http://codeforces.com/contest/707/problem/E

【题意】



给你一个n*m的方阵;

里面有k个联通块;

这k个联通块,每个连通块里面都是灯;

给你q个操作;

有以下两种类型

①将第i个连通块里面灯取反

②询问你(x1,y1)(x2,y2)这个矩形区域内灯的权值的和;

【题解】



要用到二维的树状数组;

取反操作只要O(1)就能完成;

即先不管它是什么,取反就是了;

然后在询问的时候,直接用二维树状数组累加;

这里的累加可能是减也可能是加;

也可能不变;

搞根据flag数组的值和cha数组的值来判断;

然后就是一个二维的前缀和了；

具体的看代码吧。



【完整代码】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define ps push_back

#define fi first

#define se second

#define rei(x) scanf("%d",&x)

#define rel(x) scanf("%lld",&x)

#define ref(x) scanf("%lf",&x)

typedef pair<int, int> pii;

typedef pair<LL, LL> pll;

const int dx[9] = { 0,1,-1,0,0,-1,-1,1,1 };

const int dy[9] = { 0,0,0,-1,1,-1,1,-1,1 };

const double pi = acos(-1.0);

const int K = 2e3+100;

struct abc{

    int x, y, w;

};

int n, m, k, num[K],cha[K],flag[K];

abc a[K][K];

char s[7];

LL sum[K][K];

int lowbit(int x) {return x&(-x);}

void add(int x, int y, LL t){

    while (x <= n){

        int j = y;

        while (j <= m) {

            sum[x][j] += t;

            j += lowbit(j);

        }

        x += lowbit(x);

    }

}

LL get_sum(int x, int y)

{

    LL temp = 0;

    while (x > 0){

        int j = y;

        while (j > 0){

            temp += sum[x][j];

            j -= lowbit(j);

        }

        x -= lowbit(x);

    }

    return temp;

}

int main(){

    //freopen("F:\\rush.txt", "r", stdin);

    rei(n), rei(m), rei(k);

    rep1(i, 1, k){

        rei(num[i]);

        rep1(j, 1, num[i]) rei(a[i][j].x), rei(a[i][j].y), rei(a[i][j].w);

        cha[i] = 1;

    }

    int q;

    rei(q);

    while (q--) {

        scanf("%s", s);

        if (s[0] == 'S'){

            int k; rei(k);

            cha[k] = 1 - cha[k];

        }

        else{

            rep1(i, 1, k)

                if (cha[i]){

                    rep1(j, 1, num[i]) add(a[i][j].x, a[i][j].y, a[i][j].w*((flag[i] == 0) ? 1 : -1));

                    cha[i] = 0, flag[i] = 1 - flag[i];

                }

            int x1, y1, x2, y2;

            rei(x1), rei(y1), rei(x2), rei(y2);

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

        }

    }

    //printf("\n%.2lf sec \n", (double)clock() / CLOCKS_PER_SEC);

    return 0;

}