二維樹狀數組問題。
以下是我的代碼：
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int kMaxn(1001);
int bit[kMaxn+7][kMaxn+7],book[kMaxn+7][kMaxn+7];
void Add(int x,int y,int delta)
{
for(int i=x;i<=kMaxn;i+=lowbit(i))
for(int j=y;j<=kMaxn;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()
{
int T;
scanf("%d",&T);
for(int case_num=1;case_num<=T;case_num++)
{
printf("Case %d:\n",case_num);
memset(bit,0,sizeof(bit));
memset(book,0,sizeof(book));
for(int i=1;i<=kMaxn;i++)
for(int j=1;j<=kMaxn;j++)
{
Add(i,j,1);
book[i][j]=1;
}
int Q;
scanf("%d",&Q);
while(Q--)
{
string cmd;
cin>>cmd;
if(cmd=="S")
{
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&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));
}
else if(cmd=="A")
{
int x,y,n1;
scanf("%d%d%d",&x,&y,&n1);
x++;y++;
Add(x,y,n1);
book[x][y]+=n1;
}
else if(cmd=="D")
{
int x,y,n1;
scanf("%d%d%d",&x,&y,&n1);
x++;y++;
Add(x,y,(book[x][y]-n1<0?-book[x][y]:-n1));
book[x][y]=(book[x][y]-n1<0?0:book[x][y]-n1);
}
else if(cmd=="M")
{
int x1,y1,x2,y2,n1;
scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&n1);
x1++;y1++;x2++;y2++;
if(book[x1][y1]>n1)
{
Add(x1,y1,-n1);
Add(x2,y2,n1);
book[x1][y1]-=n1;
book[x2][y2]+=n1;
}
else
{
Add(x1,y1,-book[x1][y1]);
Add(x2,y2,book[x1][y1]);
book[x2][y2]+=book[x1][y1];
book[x1][y1]=0;
}
}
}
}
return 0;
}
posted on 2011-07-31 10:55
lee1r 閱讀(327)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：數據結構