Garlands CodeForces

Garlands

 CodeForces - 707E 

题意：一个n * m矩阵，k条链(1 <= n,m,k <= 2000)，每条链绑定着一些灯泡，每个灯泡亮着时有权值，灭掉的时候权值为0。一个链条控制其上所有灯泡的亮灭。有两种操作，SWITCH i：按第i条链的开关，开变关，关变开。ASK x1,y1,x2,y2，查询以x1,y1为左上，x2,y2为右下的矩阵的权值。ASK最多2000次

题解：2000 * 2000 的数据可以使用二维的树状数组，主要是链的保证状态，当状态改变的时候如果关变开明显是加上顶点值，反之减去。在计算矩形的所有顶点值的和时候容斥一下面积就好了

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include<stack>
#define INF 0x3f3f3f3f
#define lowbit(x) (x&(-x))
using namespace std;
typedef long long LL;

const int MAXN = 2e3 + 10;
const int MOD = 1e9 + 7;

int n,m,k;
LL c[MAXN][MAXN];
struct node
{
    int len,x,y;
    LL w;
}Q[MAXN][MAXN];
int isOn[MAXN * MAXN],last[MAXN * MAXN];
void init()
{
    memset(c,0,sizeof c);
    for(int i = 1; i <= n * n; i++)
        isOn[i] = last[i] = 1;
}

void add(int x,int y,LL val)
{
    for(int i = x; i <= n; i += lowbit(i))
        for(int j = y;j <= m; j += lowbit(j))
            c[i][j] += val;
}

LL ask(int x,int y)
{
    LL ans = 0;
    for(int i = x; i > 0; i -= lowbit(i))
        for(int j = y; j > 0;j -= lowbit(j))
            ans += c[i][j];
    return ans;
}
LL all(int x1,int y1,int x2,int y2)
{
    LL ans = ask(x2,y2) - ask(x2,y1 - 1) - ask(x1 - 1,y2) + ask(x1 - 1,y1 - 1);
    return ans;
}
int main()
{
    scanf("%d %d %d",&n,&m,&k);
    init();
    for(int i = 1; i <= k; i++)
    {
        scanf("%d",&Q[i][0].len);
        for(int j = 1; j <= Q[i][0].len; j++)
        {
            scanf("%d %d %lld",&Q[i][j].x,&Q[i][j].y,&Q[i][j].w);
            add(Q[i][j].x,Q[i][j].y,Q[i][j].w);
        }
    }
    int query;
    scanf("%d",&query);
    char str[50];
    while(query--)
    {
        scanf("%s",str);
        if(str[0] == 'A')
        {
            for(int i = 1; i <= k; i++)
            {
                if(last[i] != isOn[i])//last和isOn不相同保证了这条链被动过
                {
                    for(int j = 1; j <= Q[i][0].len; j++)
                    {
                        if(isOn[i])
                            add(Q[i][j].x,Q[i][j].y,Q[i][j].w);//isOn为1代表原先为0，那么这条链上的每一个点都要加上权值
                        else
                            add(Q[i][j].x,Q[i][j].y,-Q[i][j].w);//如果isOn为0代表这条链是关闭的，这条链上的每一个点都减去权值
                    }
                    last[i] = isOn[i]; //将该条链的状态保证，以至于下次改变状态的时候可以知道和原先的状态是不一样的
                }
            }
            int x1,y1,x2,y2;
            scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
            printf("%lld
",all(x1,y1,x2,y2));
        }
        else
        {
            int tk;
            scanf("%d",&tk);
            isOn[tk] ^= 1;  //改变这条链的现有的状态
        }

    }
    return 0;
}