Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

贴个代码。第一次写树状数组,ac

Posted by zhanggt1994 at 2013-06-07 18:07:05 on Problem 1195
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator