首页 > 代码库 > 数格子

数格子

有一个S*S的方格,行和列都是从0S-1

有四种操作:      

操作

参数

含义

0

S

初始化表格,大小为S*S,所有单元格的值均为0。(此操作只出现一次且一定是第一条操作)

1

X Y A

将(XY )单元格的值增加A

2

L B R T

询问矩形区域(x,y)内的值的输出答案,其中x,y满足 L<= x <= R, B <=  y <= T

3

结束,此操作只出现一次且一定是最后一条

 

范围限制:

方格大小

S*S

1  <= S <= 1024

任意时刻单元格的值V

V

0  <= V <= 32767

每次增加的值A

A

-23768  <= A <= 23767

输入的操作总数

M

3  <= M <= 60002

所有单元格值之和

T

T  <= 230

Input

本题只有一组测试数据。

第一行为操作0

最后一行为操作3

中间操作数不多于60000

Output

输入输出格式请参考DescriptionSample

Sample Output

0 4

1 1 2 3

2 0 0 2 2

1 1 1 2

1 1 2 -1

2 1 1 2 3

3

Hint

3

4

裸的二维树状数组。

所求区域和  sum = sum(R, T) – sum(R,B-1) – sum(L-1,T) + sum(L-1,B-1)

注意S 坐标 应从1开始,所以应对输入坐标做 +1处理。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
#define S 1030
int c[S][S];
int n;
int lowbit(int x)
{
    return x&(-x);
}
void Updata(int x,int y,int val)
{
    for(int i=x; i<=n; i+=lowbit(i))
    {
        for(int j=y; j<=n; j+=lowbit(j))
        {
            c[i][j]+=val;
        }
    }
}
int Getsum(int x,int y)
{
    int sum=0;
    for(int i=x; i>0; i-=lowbit(i))
    {
        for(int j=y; j>0; j-=lowbit(j))
        {
            sum+=c[i][j];
        }
    }
    return sum;
}
int main()
{
    int tt, cmd, x, y, val;
    int x1, y1, x2, y2;
    freopen("B.in","r",stdin);
    freopen("X.out","w",stdout);
    scanf("%d%d",&tt,&n);
    memset(c,0,sizeof(c));
    while(scanf("%d",&cmd) && cmd<3)
    {
        if(cmd==1)
        {
            scanf("%d%d%d",&x,&y,&val);
            x++;
            y++;
            Updata(x,y,val);
        }
        else if(cmd==2)
        {
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            x1++, y1++, x2++, y2++;
            int ans=Getsum(x2,y2)-Getsum(x2,y1-1)-Getsum(x1-1,y2)+Getsum(x1-1,y1-1);
            printf("%d\n",ans);
        }
    }
    return 0;
}