http://acm.hdu.edu.cn/showproblem.php?pid=1892
二维树状数组求子段和
#include <iostream>
using namespace std;
const int MAX=1002;
int a[MAX][MAX],c[MAX][MAX];
int lowbit(int i)
{
return i&(-i);
}
int max(int i,int j)
{
return i>j? i:j;
}
int min(int i,int j)
{
return i<j? i:j;
}
void modify(int x,int y,int num)
{
int i,j;
for(i=x;i<MAX;i+=lowbit(i))
for(j=y;j<MAX;j+=lowbit(j))
c[i][j]+=num;
}
int sum(int x,int y)
{
int s=0,i,j;
for(i=x;i>0;i-=lowbit(i))
for(j=y;j>0;j-=lowbit(j))
s+=c[i][j];
return s;
}
void init()
{
int i,j;
for(i=1;i<MAX;i++)
for(j=1;j<MAX;j++)
{
a[i][j]=1;
c[i][j]=lowbit(i)*lowbit(j);
}
}
int main()
{
int i,n,t,j,s,x1,x2,y1,y2,maxx,maxy,minx,miny,temp,x,y,num;
char ch;
scanf("%d",&t);
for(i=1;i<=t;i++)
{
init();
scanf("%d",&n);
printf("Case %d:\n",i);
while(n--)
{
getchar();
scanf("%c ",&ch);
if(ch=='S')
{
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
x1++;y1++;x2++;y2++;
maxx=max(x1,x2);
maxy=max(y1,y2);
minx=min(x1,x2);
miny=min(y1,y2);
temp=sum(maxx,miny-1)+sum(minx-1,maxy)-sum(minx-1,miny-1);
s=sum(maxx,maxy)-temp;
printf("%d\n",s);
continue;
}
if(ch=='A')
{
scanf("%d %d %d",&x,&y,&num);
x++;y++;
a[x][y]+=num;
modify(x,y,num);
continue;
}
if(ch=='D')
{
scanf("%d %d %d",&x,&y,&num);
x++;y++;
if(num>a[x][y])
num=a[x][y];
a[x][y]-=num;
modify(x,y,-num);
continue;
}
if(ch=='M')
{
scanf("%d %d %d %d %d",&x1,&y1,&x2,&y2,&num);
x1++;y1++;x2++;y2++;
if(num>a[x1][y1])
num=a[x1][y1];
a[x1][y1]-=num;
a[x2][y2]+=num;
modify(x1,y1,-num);
modify(x2,y2,num);
continue;
}
}
}
return 0;
}
posted on 2011-09-03 10:49
大大木马 阅读(181)
评论(0) 编辑 收藏 引用