HDU 1892(See you~ 简单二维树状数组)

spoiler posted @ 2011年5月09日 20:36 in 树状数组经典题目 , 1870 阅读

题目大意:
S x1 y1 x2 y2 means you should tell me the total books of the rectangle used (x1,y1)-(x2,y2) as the diagonal, including the two points.
A x1 y1 n1 means I put n1 books on the position (x1,y1)
D x1 y1 n1 means I move away n1 books on the position (x1,y1), if less than n1 books at that position, move away all of them.
M x1 y1 x2 y2 n1 means you move n1 books from (x1,y1) to (x2,y2), if less than n1 books at that position, move away all of them.

就这几个操作

题目分析:

这题唯一注意的地方是给出的点不一定是前面的比后面的小,我是说查询以这两点为对角线的矩形里面的书的数量的时候,还有你要更新到1001,因为你为防止0的死循环,所以把每个坐标,都加1 这样可以防止死循环;如果他输入 是(1000 ,1000) ,你要计算的是(1001,1001) 所以你要更新到1001!

#include<iostream>
#include<cstdio>
#include<cstring>
#define lowbit(x) (x&(-x))
using namespace std;
int s[1005][1005],num[1005][1005];
int getsum(int x,int y){
	int t,sum;
	sum=0;
	while(x>0){
		t=y;
		while(t>0){
			sum+=s[x][t];
			t-=lowbit(t);
		}
		x-=lowbit(x);
	}
	return sum;
}
void modify(int x,int y,int count){
	int t;
	while(x<=1001){
		t=y;
		while(t<=1001){
			s[x][t]+=count;
			t+=lowbit(t);
		}
		x+=lowbit(x);
	}
	return ;
}
int main(){
	int cas,times,i,j,k;
	int x1,x2,y1,y2,n;
	int maxx,maxy,minx,miny;
	char ch[10];
	scanf("%d",&cas);
	for(k=1;k<=cas;k++){
		printf("Case %d:\n",k);
		for(i=1;i<=1002;i++)
			for(j=1;j<=1002;j++){
				num[i][j]=1;
				s[i][j]=lowbit(i)*lowbit(j);
			}
		scanf("%d",×);
		while(times--){
			scanf("%s",ch);
			if(ch[0]=='S'){
				scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
				x1++; y1++; x2++; y2++;
				maxx=x1>x2?x1:x2;
				maxy=y1>y2?y1:y2;
				minx=x1<x2?x1:x2;
				miny=y1<y2?y1:y2;
				x2=maxx; x1=minx;
				y2=maxy; y1=miny;
				int ans=getsum(x2,y2)-getsum(x1-1,y2)-getsum(x2,y1-1)+getsum(x1-1,y1-1);
				printf("%d\n",ans);
			}
			if(ch[0]=='A'){
				scanf("%d %d %d",&x1,&y1,&n);
				x1++; y1++;
				num[x1][y1]+=n;
				modify(x1,y1,n);
			}
			if(ch[0]=='D'){
				scanf("%d %d %d",&x1,&y1,&n);
				x1++; y1++;
				if(num[x1][y1]<=n){
					n=num[x1][y1];
				}
				num[x1][y1]-=n;
				n=-n;
				modify(x1,y1,n);
			}
			if(ch[0]=='M'){
				scanf("%d %d %d %d %d",&x1,&y1,&x2,&y2,&n);
				x1++; y1++; x2++; y2++;
				if(num[x1][y1]<=n){
					n=num[x1][y1];		
				}
				num[x1][y1]-=n;
				num[x2][y2]+=n;
				modify(x1,y1,-n);
				modify(x2,y2,n);
			}
		}
	}
	return 0;
}




 

Avatar_small
hello kity 说:
2011年12月17日 03:46

关于树状数组的学习 这里推荐大家一个大牛的文章 谢谢各位的光临我的博客 http://hi.baidu.com/czyuan_acm/blog/item/49f02acb487f06f452664fbc.html


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter