Hotel [POJ

Hotel POJ - 3667 T3 D3

线段树区间修改 、区间合并

思路：

1表示当前车位无车，0表示有

llen 表示当前区间左端点向右连续的1的个数

rlen 表示当前区间右端点向左连续的1的个数

sum 表示当前区间最大连续1的个数

用线段树维护 llen, rlen,sum

询问时：

• 若左子树的sum大于查询长度len，递归左子树
• 若左子树的rlen+右子树的llen大于len，则返回左子树的rlen起点，即为答案
• 前两种情况都不满足，递归右子树

参考代码

/*
               #########                       
              ############                     
              #############                    
             ##  ###########                   
            ###  ###### #####                  
            ### #######   ####                 
           ###  ########## ####                
          ####  ########### ####               
        #####   ###########  #####             
       ######   ### ########   #####           
       #####   ###   ########   ######         
      ######   ###  ###########   ######       
     ######   #### ##############  ######      
    #######  ##################### #######     
    #######  ##############################    
   #######  ###### ################# #######   
   #######  ###### ###### #########   ######   
   #######    ##  ######   ######     ######   
   #######        ######    #####     #####    
    ######        #####     #####     ####     
     #####        ####      #####     ###      
      #####      ;###        ###      #        
        ##       ####        ####              
*/
#include<iostream>
#include<algorithm>
#include<math.h>
#define ll long long 
#define ls (p<<1)
#define rs ((p<<1)|1)
#define mid ((t[p].l+t[p].r)>>1) 
using namespace std;
int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void Prin(int x){if(x < 0){putchar('-');x = -x;}if(x > 9) Prin(x / 10);putchar(x % 10 + '0');}
const int qs=1e5+7;
struct Tree{
	int l,r,llen,rlen,sum,add;
	#define l(x) t[x].l
	#define r(x) t[x].r
	#define llen(x) t[x].llen
	#define rlen(x) t[x].rlen
	#define sum(x) t[x].sum
	#define add(x) t[x].add
}t[qs<<2];


void pushup(int p){
	llen(p)=llen(ls)+(llen(ls)==r(ls)-l(ls)+1 ? llen(rs) : 0);
	rlen(p)=rlen(rs)+(rlen(rs)==r(rs)-l(rs)+1 ? rlen(ls) : 0);
	sum(p)=max(max(sum(ls),sum(rs)),rlen(ls)+llen(rs));
}

void build(int p,int l,int r){
	l(p)=l,r(p)=r;
	add(p)=-1;
	if(l==r) {
		llen(p)=rlen(p)=1;
		sum(p)=1; 
		return;
	}
	build(ls,l,mid);
	build(rs,mid+1,r);
	pushup(p);
}

void down(int p){
	if(add(p)==-1) return;
	llen(ls)=rlen(ls)=sum(ls)=(r(ls)-l(ls)+1)*add(p);
	llen(rs)=rlen(rs)=sum(rs)=(r(rs)-l(rs)+1)*add(p);
	add(ls)=add(rs)=add(p);
	add(p)=-1;
}

void update(int p,int l,int r,int k){
	if(l<=l(p)&&r>=r(p)){
		llen(p)=rlen(p)=sum(p)=(r(p)-l(p)+1)*k;
		add(p)=k;
		return;
	}
	down(p);
	if(l<=mid) update(ls,l,r,k);
	if(r>mid) update(rs,l,r,k);
	pushup(p);
}

int ask(int p,int len){
	if(l(p)==r(p)) return 1;
	down(p);
	if(sum(ls)>=len) return ask(ls,len);
	else if(llen(rs)+rlen(ls)>=len) return mid-rlen(ls)+1;
	else return ask(rs,len);
	return 0;
} 

int n,q;
int main(){
	n=read(),q=read();
	build(1,1,n);
	while(q--){
		int x,l,len;
		x=read();
		if(x==1){
			len=read();
			if(sum(1)<len){
				puts("0");
				continue;
			}
			int ans=ask(1,len);
			Prin(ans);
			puts("");
			update(1,ans,ans+len-1,0);
		}
		else {
			l=read(),len=read();
			update(1,l,l+len-1,1);
		}
	}
	
	
	return 0;
}