POJ 3667 hotel（线段树经典题目）
题目大意：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;
}
评论 (0)