【2018年全国多校算法寒假训练营练习比赛(第五场)-E】情人节的电灯泡(二维树状数组单点更新+区间查询)

试题链接：https://www.nowcoder.com/acm/contest/77/E

题目描述

情人节到了，小芳和小明手牵手，打算过一个完美的情人节，但是小刚偏偏也来了，当了一个明晃晃的电灯泡，小明很尴尬，就和小刚说，我交给你个任务，你完成了我俩就带你玩，否则你就回家吧。小刚很有当单身狗的觉悟，他坚决不想让小明过好情人节，同为单身狗的你能帮帮他吗？现在有一个n×n（1 <= n <= 1000）的格子，每一个格子都有一个电灯泡，可能是亮的，也可能是灭的（1代表亮， 0代表灭），现在有两种操作，一种是给你一个坐标，对于那个坐标上的灯泡，如果他是亮的，那么熄灭他，反之如果他是灭的，那么打开它。第二种操作是给你两个坐标，第一个坐标代表一个子矩阵的左上角，另一个坐标是右下角，请你求出当前子矩阵中有多少个灯泡是亮着的。燥起来吧！！！单身狗们！！！！

输入描述:

第一行两个整数，n（1 <= n <= 1000）和m（1 <= m <= 100000），分别代表正方形格子的边长和询问次数。
接下来n行，每一行有n个bool形数字（0或1），代表灯泡的状态。
接下来m行，每一行第一个数字f（1或2）代表操作的类型，如果f是1，那么接下来输入一个坐标（x, y）(1 <= x, y <= n)，对于当前位置的灯泡状态进行改变，如果是2，那么接下来输入两个坐标（x1, y1）(1 <= x1, y1 <= n)， （x2, y2）(1 <= x2, y2 <= n)，确定子矩阵的位置，输出子矩阵中亮着的灯泡数量并换行。

输出描述:

对于每一个2操作，输出子矩阵中亮着的灯泡数量并换行。

输入

6 4

0 0 1 0 1 0

1 0 1 1 0 1

1 0 0 0 0 0

1 1 0 0 1 0

0 0 0 0 1 1

0 0 0 0 1 0

2 2 2 4 5

1 1 1

2 1 1 6 6

1 2 6

输出

4

14

代码

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<cstdlib>

#include<cmath>

using namespace std;

const int N = ;

typedef long long LL;

int c[N][N], n;

int lowbit(int t)

{

    return t&(-t);

}

void update(int x,int y,int m)

{

    for(int i=x; i<=n; i+=lowbit(i))

        for(int j=y; j<=n; j+=lowbit(j))

            c[i][j]+=m;

}

int query(int x,int y)

{

    int sum=;

    for(int i=x; i>; i-=lowbit(i))

        for(int j=y; j>; j-=lowbit(j))

            sum+=c[i][j];

    return sum;

}

int main()

{

    int i,j,m,k;

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

    for(i=; i<=n; i++)

        for(j=; j<=n; j++)

        {

            scanf("%d",&k);

            update(i,j,k);

        }

    while(m--)

    {

        int t,x,y;

        scanf("%d", &t);

        if(t==)

        {

            scanf("%d%d",&x,&y);

            int s1=query(x,y)-query(x-,y)-query(x,y-)+query(x-,y-);

            if(s1) update(x,y,-);

            else update(x,y,);

        }

        else

        {

            int x1,x2,y1,y2;

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

            printf("%d\n", query(x2,y2)-query(x1-,y2)-query(x2,y1-)+query(x1-,y1-));

        }

    }

    return ;

}

巴特西

【2018年全国多校算法寒假训练营练习比赛(第五场)-E】情人节的电灯泡(二维树状数组单点更新+区间查询)

题目描述

输入描述:

输出描述:

输入

输出

代码

最新文章

热门文章