二維樹狀數(shù)組的應(yīng)用。每次在某個(gè)點(diǎn)上增加一個(gè)值，或是詢問某塊區(qū)域內(nèi)的和。
以下是我的代碼：
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int n(1001);
int bit[n+7][n+7];
bool bright[n+7][n+7];
void Add(int x,int y,int delta)
{
for(int i=x;i<=n;i+=lowbit(i))
for(int j=y;j<=n;j+=lowbit(j))
bit[i][j]+=delta;
}
int Sum(int x,int y)
{
int re(0);
for(int i=x;i>0;i-=lowbit(i))
for(int j=y;j>0;j-=lowbit(j))
re+=bit[i][j];
return re;
}
int main()
{
memset(bit,0,sizeof(bit));
memset(bright,false,sizeof(bright));
int m;
cin>>m;
while(m--)
{
string cmd;
cin>>cmd;
if(cmd=="B")
{
int x,y;
scanf("%d%d",&x,&y);
x++;y++;
if(!bright[x][y])
Add(x,y,1);
bright[x][y]=true;
}
else if(cmd=="D")
{
int x,y;
scanf("%d%d",&x,&y);
x++;y++;
if(bright[x][y])
Add(x,y,-1);
bright[x][y]=false;
}
else if(cmd=="Q")
{
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&x2,&y1,&y2);
x1++;y1++;x2++;y2++;
if(x1>x2)
swap(x1,x2);
if(y1>y2)
swap(y1,y2);
printf("%d\n",Sum(x2,y2)-Sum(x1-1,y2)-Sum(x2,y1-1)+Sum(x1-1,y1-1));
}
}
return 0;
}
posted on 2011-07-31 09:29
lee1r 閱讀(277)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：數(shù)據(jù)結(jié)構(gòu)