[Vijos1512] SuperBrother 打鼹鼠

2014-11-06
竞赛题解 / 高级数据结构
Vijos树状数组

描述 Description

在这个 “打鼹鼠” 的游戏中，鼹鼠会不时地从洞中钻出来，不过不会从洞口钻进去（鼹鼠真胆大……）。洞口都在一个大小为 n(n<=1024)的正方形中。这个正方形在一个平面直角坐标系中，左下角为(0,0)，右上角为(n-1,n-1)。洞口所在的位置都是整点，就是横纵坐标都为整数的点。而 SuperBrother 也不时地会想知道某一个范围的鼹鼠总数。这就是你的任务。

输入格式 InputFormat

每个输入文件有多行。
第一行，一个数 n，表示鼹鼠的范围。
以后每一行开头都有一个数 m，表示不同的操作：
m=1，那么后面跟着 3 个数 x,y,k(0<=x,y4
>1 2 2 5
>2 0 0 2 3
>3

样例输出 SampleOutput

5

Vijos 1512

代码 Code

二维树状数组。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1030;
int i,j,t,n,m,l,r,k,z,y,x;
int tree[maxn][maxn];
int x1,x2,y1,y2,ans;
inline int lowbit(int s)
{
    return s&(-s);
}
inline void ins(int x,int y,int s)
{
    int i,j,t;
    for (i=x;i<maxn;i+=lowbit(i)) for (j=y;j<maxn;j+=lowbit(j)) tree[i][j]+=s;
}
inline int sum(int x,int y)
{
    int i,j,t=0;
    for (i=x;i>0;i-=lowbit(i)) for (j=y;j>0;j-=lowbit(j)) t+=tree[i][j];
    return t;
}
int main()
{
    scanf("%d",&n);
    while (scanf("%d",&m))
    {
        if (m==3) break;
        if (m==1)
        {
            scanf("%d%d%d",&x,&y,&z);
            x++;y++;
            ins(x,y,z);
        }
        if (m==2)
        {
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            x1++;y1++;x2++;y2++;
            ans=sum(x2,y2)+sum(x1-1,y1-1)-sum(x2,y1-1)-sum(x1-1,y2);
            printf("%d\n",ans);
        }
    }
    return 0;
}