| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
贴个代码。第一次写树状数组,ac#include<iostream>
#include<stdio.h>
using namespace std;
int a[1026][1026];
int lowbit(int x)
{
return x&(-x);
}
void add(int x,int y,int n,int val)
{
for(int i=x;i<=n;i+=lowbit(i))
{
for(int j=y;j<=n;j+=lowbit(j))
{
a[i][j]+=val;
}
}
}
int sum(int x,int y)
{
int res=0;
for(int i=x;i>0;i-=lowbit(i))
for(int j=y;j>0;j-=lowbit(j))
res+=a[i][j];
return res;
}
int main()
{
int cas,n;
while(scanf("%d",&cas))
{
if(cas==3)
break;
if(cas==0)
{
scanf("%d",&n);
memset(a,0,sizeof(a));
}
if(cas==1)
{
int x,y,t;
scanf("%d %d %d",&x,&y,&t);
add(x+1,y+1,n,t);
}
if(cas==2)
{
int x1,x2,y1,y2;
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
printf("%d\n",sum(x2+1,y2+1)+sum(x1,y1)-sum(x1,y2+1)-sum(x2+1,y1));
}
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator