622
HDU 1892 二維樹狀數組
題意給的操作講的很明白 注意不能出現負數 坐標值可能為0 兩個坐標大小不能確定
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1002;
int tree[maxn + 2][maxn + 2];
int n;
inline int Lowbit(int x)
{
return x&(-x);
}
inline void Update(int x,int y,int v)
{
for(int i=x; i<=maxn; i+=Lowbit(i))
for(int j=y; j<=maxn; j+=Lowbit(j))
tree[i][j]+=v;
}
inline int Query(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+=tree[i][j];
return sum;
}
inline int getv(int x,int y)
{
return Query(x,y)-Query(x-1,y)-Query(x,y-1)+Query(x-1,y-1);
}
int main()
{
int t,n,cas=0;
char c[2];
cin>>t;
while(t--)
{
scanf("%d",&n);
memset(tree,0,sizeof(tree));
for(int i=1; i<=maxn; i++)
for(int j=1; j<=maxn; j++)
Update(i,j,1);
printf("Case %d:\n",++cas);
while(n--)
{
scanf("%s",c);
if(c[0]=='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);
int s=Query(x2,y2)-Query(x1-1,y2)-Query(x2,y1-1)+Query(x1-1,y1-1);
printf("%d\n",s);
}
else if(c[0]=='A')
{
int x,y,n;
scanf("%d%d%d",&x,&y,&n);
x++,y++;
Update(x,y,n);
}
else if(c[0]=='D')
{
int x,y,n;
scanf("%d%d%d",&x,&y,&n);
x++,y++;
int s=getv(x,y),d=n<s?n:s;
Update(x,y,-d);
}
else if(c[0]=='M')
{
int x1,y1,x2,y2,n;
scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&n);
x1++,y1++,x2++,y2++;
int s=getv(x1,y1),d=n<s?n:s;
Update(x2,y2,d);
Update(x1,y1,-d);
}
}
}
return 0;
}
最後更新：2017-04-04 07:03:45