POJ 3667 hotel(线段树经典题目)

spoiler posted @ 2011年3月31日 16:26 in ACM经典题目之线段树 , 2341 阅读

题目大意:Bessie等牛到加拿大的桑德贝去增长文化修养外带观赏苏必利尔湖的阳光。按照导游的介绍,Bessie选择了著名的Cumberland大街上的Bullmoose宾馆作为居住的地点。

这座巨型宾馆在一条超长走廊上有N(1 ≤ N ≤ 50000)个排成一排的房间,每个房间都能欣赏到苏必利尔湖的好景色。现在所有的房间都是空的。

现在Bessie等旅客们正在不断地发出订房和退房要求。你需要接受M(1 ≤ M < 50000)条指令:

每条指令的第一个数字为1或2。如果是1,后面将有一个整数D表示顾客要预定的房间数。注意,这些房间必须是连续的。如果能够满足旅客的订房要求, 输出满足要求的第一个房间的编号(例如,要订房6间,输出3表示3, 4, 5, 6, 7, 8是满足要求的),这样的编号必须是可能的编号里面最靠前的。如果不能满足要求,输出0。

如果是2,后面将有两个整数X和D表示顾客要退掉X, X + 1, X + 2, ... , X + D - 1这D间房。对于这样的指令什么都不输出

题意分析:刚开始拿到这个题目也是不知道怎么建树,树节点里存放哪些信息,后来花了很久研究了解题报告,终于搞明白了。当你要查询连续的40个房间时候,左边有30个 右边有30个,你该怎么选择呢?这个时候如果用枚举各种情况 在逻辑上是可以的,但是肯定TLE。所以为了达到这种目的,我们要在节点里存放:lv(从左边数起,最大连续的房间数目),rv(以右边第一点为起点,开始计数的最大连续房间数),flag表示区间能否使用的(flag为0 表示可以使用),cav(指这个区间连续空余房间的最大值,相当于:lv,rv和交界处3个中的最大值),交界情况是指(左子树的)rv+(右子树的)lv,自己在纸上画一下,很明朗的;

建树的过程跟常规的 差不多,就是刚开始把rv,lv,cav初始化成当前节点区间的长度,因为题目给出初始情况,都是可以住人的,稍微注意一下,当num等于1时,flag赋值为1,因为这样在后面的操作,才能往下传递数值。

建立一个整理函数 ,当flag=0的时候整理当前节点的数值,把当前节点的rv,lv,cav,都更新成该区间长度。

查询操作:首先当前节点的数值往下传递,整理左右子树的rv,lv,cav;当查询到节点时,并且查询长度为1,则结束这次查询;先查询左子树是否有这么多空余房间,不行就查询左右交界处是否有这么多空余房间(即左子树的rv+右子树的lv),再查询右子树是否有这么多空余房间,如果都没,则返回0,结束查询。

更新操作注意的地方很多,首先更新的过程节点的值还得往下传递,这样保证了下一次在子节点的查询,当查询区间大于节点区间时,整理该区间,并且flag=-1标记该区间不能使用了;如果查询区间小于该 区间,则分别讨论左子树,右子树,注意一下两点,划分左右子树的界限是:x>=s[num].a和y>=mid+1;还有一个要注意的是,对左右子树更新完了 然后要回朔向上更新其父亲节点,因为父亲的lv就是左儿子的lv,画个图就能明白了,特别考虑一下:当s[num+num].lv==len(num+num)也就是说整个区间都是可以用的,那么父亲的s[num].lv=s[num].lv+s[num+num].lv;同理rv也是如此;

代码如下:

#include<iostream>
#include<stdio.h>
using namespace std;

struct node{
#include<iostream>
#include<stdio.h>
using namespace std;

struct node{
  int a,b;
  int rv,lv,cav,flag;
}s[200020];

int len(int x){
    return s[x].b-s[x].a+1;
}
int max(int x,int y){
	return x>y?x:y;
}

void init(int x){
   s[x].rv=s[x].lv=s[x].cav=s[x].flag?0:len(x);
}

int Build(int x,int y,int num){
   s[num].a=x;   s[num].b=y;
   s[num].lv=s[num].rv=s[num].cav=len(num);
   s[num].flag=num==1?0:-1;
   if(x==y)//
      return 0;
   int mid=(s[num].a+s[num].b)/2;//
   Build(x,mid,num+num);
   Build(mid+1,y,num+num+1);
   return 0;
}

int search(int num,int l){
   if(len(num)==1&&l==1)
      return s[num].a;
   if(s[num].flag!=-1){
      s[num+num].flag=s[num+num+1].flag=s[num].flag;
      s[num].flag=-1;
      init(num+num);
      init(num+num+1);
   }
   if(s[num+num].cav>=l)
      return search(num+num,l);
   else if(s[num+num].rv+s[num+num+1].lv>=l)
       return s[num+num].b-s[num+num].rv+1;
   else if(s[num+num+1].cav>=l)
      return search(num+num+1,l);
   else return 0;
}

int update(int x,int y,int flag,int num){
    if(x<=s[num].a&&y>=s[num].b){
         s[num].flag=flag;
         init(num);    
         return 0;
    }
    if(s[num].flag!=-1){
       s[num+num].flag=s[num+num+1].flag=s[num].flag;
       s[num].flag=-1;
       init(num+num);   init(num+num+1);
    }
    int mid=(s[num].a+s[num].b)/2;
    if(x<=mid)
         update(x,y,flag,num+num);//
    if(y>=mid+1)
         update(x,y,flag,num+num+1);//当初加了 else得出错误答案
    s[num].lv=s[num+num].lv;
    s[num].rv=s[num+num+1].rv;
    s[num].cav=max(max(s[num+num].cav,s[num+num+1].cav),s[num+num].rv+s[num+num+1].lv);
    if(s[num].lv==len(num+num))
        s[num].lv+=s[num+num+1].lv;
    if(s[num].rv==len(num+num+1))
        s[num].rv+=s[num+num].rv;

}

int main(){
	int n,cas,i,t,x,y;
	scanf("%d %d",&n,&cas);
	Build(1,n,1);
	for(i=1;i<=cas;i++){
		scanf("%d",&t);
		if(t==1){
			scanf("%d",&x);
			int k=search(1,x);
			printf("%d\n",k);
			if(k)
				update(k,k+x-1,1,1);
		}
		else if(t==2){
			scanf("%d %d",&x,&y);
			update(x,x+y-1,0,1);
		}
	}
	return 0;
}

  int a,b;
  int rv,lv,cav,flag;
}s[200020];

int len(int x){
    return s[x].b-s[x].a+1;
}

void init(int x){
   s[x].rv=s[x].lv=s[x].cav=s[x].flag?0:len(x);
}

int Build(int x,int y,int num){
   s[num].lv=s[num].rv=s[num].cav=len(num);
   s[num].a=x;   s[num].b=y;
   s[num].flag=num==1?0:-1;
   if(x=y)
      return 0;
   int mid=(s[num].a+s[num].b)/2
   Build(x,mid,num+num);
#include<iostream>
#include<stdio.h>
using namespace std;

struct node{
  int a,b;
  int rv,lv,cav,flag;
}s[200020];

int len(int x){
    return s[x].b-s[x].a+1;
}
int max(int x,int y){
	return x>y?x:y;
}

void init(int x){
   s[x].rv=s[x].lv=s[x].cav=s[x].flag?0:len(x);
}

int Build(int x,int y,int num){
   s[num].a=x;   s[num].b=y;
   s[num].lv=s[num].rv=s[num].cav=len(num);
   s[num].flag=num==1?0:-1;
   if(x==y)//
      return 0;
   int mid=(s[num].a+s[num].b)/2;//
   Build(x,mid,num+num);
   Build(mid+1,y,num+num+1);
   return 0;
}

int search(int num,int l){
   if(len(num)==1&&l==1)
      return s[num].a;
   if(s[num].flag!=-1){
      s[num+num].flag=s[num+num+1].flag=s[num].flag;
      s[num].flag=-1;
      init(num+num);
      init(num+num+1);
   }
   if(s[num+num].cav>=l)
      return search(num+num,l);
   else if(s[num+num].rv+s[num+num+1].lv>=l)
       return s[num+num].b-s[num+num].rv+1;
   else if(s[num+num+1].cav>=l)
      return search(num+num+1,l);
   else return 0;
}

int update(int x,int y,int flag,int num){
    if(x<=s[num].a&&y>=s[num].b){
         s[num].flag=flag;
         init(num);    
         return 0;
    }
    if(s[num].flag!=-1){
       s[num+num].flag=s[num+num+1].flag=s[num].flag;
       s[num].flag=-1;
       init(num+num);   init(num+num+1);
    }
    int mid=(s[num].a+s[num].b)/2;
    if(x<=mid)
         update(x,y,flag,num+num);//
    if(y>=mid+1)
         update(x,y,flag,num+num+1);//当初加了 else得出错误答案
    s[num].lv=s[num+num].lv;
    s[num].rv=s[num+num+1].rv;
    s[num].cav=max(max(s[num+num].cav,s[num+num+1].cav),s[num+num].rv+s[num+num+1].lv);
    if(s[num].lv==len(num+num))
        s[num].lv+=s[num+num+1].lv;
    if(s[num].rv==len(num+num+1))
        s[num].rv+=s[num+num].rv;

}

int main(){
	int n,cas,i,t,x,y;
	scanf("%d %d",&n,&cas);
	Build(1,n,1);
	for(i=1;i<=cas;i++){
		scanf("%d",&t);
		if(t==1){
			scanf("%d",&x);
			int k=search(1,x);
			printf("%d\n",k);
			if(k)
				update(k,k+x-1,1,1);
		}
		else if(t==2){
			scanf("%d %d",&x,&y);
			update(x,x+y-1,0,1);
		}
	}
	return 0;
}

 


登录 *


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