1195.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"stdio.h"

int sum[1025][1025],s;

inline int lowbit(int a)
{
	return a&(a^(a-1));
}

void init()
{
	int i,j;
	
	scanf("%d",&s);
	
	for(i=1;i<=s;i++)
	for(j=1;j<=s;j++)
		sum[i][j]=0;
}

void set()
{
	int x,y,a,j;

	scanf("%d %d %d",&x,&y,&a);
	
	x++,y++;

	while(x<=s)
	{
		for(j=y;j<=s;j+=lowbit(j))
		{
			sum[x][j]+=a;
		}
		x+=lowbit(x);
	}
}

int count(int x,int y)
{
	int ans=0,j;
	
	while(x>0)
	{
		for(j=y;j>0;j-=lowbit(j))
		{
			ans+=sum[x][j];
		}
		x-=lowbit(x);
	}

	return ans;
}


int query()
{
	int l,b,r,t;

	scanf("%d %d %d %d",&l,&b,&r,&t);

	l++,b++,r++,t++;

	return count(r,t)-count(r,b-1)-count(l-1,t)+count(l-1,b-1);
}

int main()
{
	int c;
	while(1)
	{
		scanf("%d",&c);
		
		switch(c){
		case 0:init();break;
		case 1:set();break;
		case 2:printf("%d\n",query());break;
		case 3:return 0;
		}
	}
	return 0;
}