【HDU1892】See you~(二维树状数组)

Categories: 数据结构和算法
Tags: ,
Comments: No Comments
Published on: 2011 年 05 月 11 日

Now I am leaving hust acm. In the past two and half years, I learned so many knowledge about Algorithm and Programming, and I met so many good friends. I want to say sorry to Mr, Yin, I must leave now ~~>.<~~. I am very sorry, we could not advanced to the World Finals last year.
When coming into our training room, a lot of books are in my eyes. And every time the books are moving from one place to another one. Now give you the position of the books at the early of the day. And the moving information of the books the day, your work is to tell me how many books are stayed in some rectangles.
To make the problem easier, we divide the room into different grids and a book can only stayed in one grid. The length and the width of the room are less than 1000. I can move one book from one position to another position, take away one book from a position or bring in one book and put it on one position.

#include<iostream>
using namespace std;
int const maxn=1010;
int tab[maxn][maxn];
const int _size=1005;

int lowbit(int n){return n&(-n);}

void add(int x,int y,int v){
	for(int i=x;i<=_size;i+=lowbit(i))
		for(int j=y;j<=_size;j+=lowbit(j))
			tab[i][j]+=v;
}
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+=tab[i][j];
	return res;
}
int getv(int x,int y){
	return sum(x,y)+sum(x-1,y-1)-sum(x,y-1)-sum(x-1,y);
}
int main()
{
	freopen("in.txt","r",stdin);
	int t,x1,y1,x2,y2,v;cin>>t;
	char ch[3];
	int cou=0;
	while(t--){
		cout<<"Case "<<++cou<<":"<<endl;
		memset(tab,0,sizeof(tab));
		for(int i=1;i<_size;i++)
			for(int j=1;j<_size;j++)
				add(i,j,1);
		int n;cin>>n;
		while(n--){
			scanf("%s",ch);
			if(ch[0]=='A'){
				scanf("%d%d%d",&x1,&y1,&v);
				add(x1+1,y1+1,v);
			}else if(ch[0]=='S'){
				scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
				if(x1>x2)swap(x1,x2);
				if(y1>y2)swap(y1,y2);
				printf("%d\n",sum(x2+1,y2+1)+sum(x1,y1)-sum(x1,y2+1)-sum(x2+1,y1));
			}else if(ch[0]=='D'){
				scanf("%d%d%d",&x1,&y1,&v);
				int v1=getv(x1+1,y1+1);
				add(x1+1,y1+1,-min(v,v1));
			}else if(ch[0]=='M'){
				scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&v);
				int v1=getv(x1+1,y1+1);
				v1=min(v1,v);
				add(x1+1,y1+1,-v1);
				add(x2+1,y2+1,v1);
			}
		}
	}

}

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期六, 2017 年 10 月 21 日