【算法】线段树（经典线段树上二分）
【题意】n个房间，m个询问，每次订最前的连续x个的空房间，或退订从x开始y个房间，求每次订的最左房间号。
【题解】关键在于找连续x个空房间，经典二分。
线段树标记sum,lsum,rsum，表示最长连续房间，从左开始最长连续房间，从右开始最长连续房间。
对于区间k，如果k.sum<x，则无解。
否则，如果l(k).sum>=x，则在左区间。
否则，如果l(k).rsum+r(k).lsum>=x，则在中间，那么l(k).r-l(k).rsum+1就是答案。
否则，则在右区间。
这样可以准确的定位，也体现了线段树被称之为区间树的特点，可以将询问分成若干个完整的区间，只要维护区间信息即可。
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=;
struct tree{int l,r,lsum,rsum,sum,delta;}t[maxn*];
int n,m; void build(int k,int l,int r){
t[k].l=l;t[k].r=r;t[k].sum=t[k].lsum=t[k].rsum=r-l+;t[k].delta=-;
if(l==r)return;
int mid=(l+r)>>;
build(k<<,l,mid);build(k<<|,mid+,r);
}
void modify(int k,int x){
if(x==){
t[k].lsum=t[k].rsum=t[k].sum=;
}
else{
t[k].lsum=t[k].rsum=t[k].sum=t[k].r-t[k].l+;
}
}
void update(int k){
t[k].sum=max(t[k<<].rsum+t[k<<|].lsum,max(t[k<<].sum,t[k<<|].sum));
t[k].lsum=t[k<<].lsum;if(t[k<<].lsum==t[k<<].r-t[k<<].l+)t[k].lsum+=t[k<<|].lsum;
t[k].rsum=t[k<<|].rsum;if(t[k<<|].rsum==t[k<<|].r-t[k<<|].l+)t[k].rsum+=t[k<<].rsum;
}
void push_down(int k){
if(~t[k].delta){
modify(k<<,t[k].delta);t[k<<].delta=t[k].delta;
modify(k<<|,t[k].delta);t[k<<|].delta=t[k].delta;//传标记
t[k].delta=-;
}
}
int ask(int k,int x){
push_down(k);
if(t[k].sum<x)return ;
if(t[k<<].sum>=x)return ask(k<<,x);
if(t[k<<].rsum+t[k<<|].lsum>=x)return t[k<<].r-t[k<<].rsum+;
return ask(k<<|,x);
}
void insert(int k,int l,int r,int x){
if(l<=t[k].l&&t[k].r<=r)t[k].delta=x,modify(k,x);//打标记
else{
push_down(k);
int mid=(t[k].l+t[k].r)>>;
if(l<=mid)insert(k<<,l,r,x);
if(r>mid)insert(k<<|,l,r,x);
update(k);
}
} int main(){
scanf("%d%d",&n,&m);
build(,,n);
int p,x,y;
for(int i=;i<=m;i++){
scanf("%d",&p);
if(p==){
scanf("%d",&x);
printf("%d\n",y=ask(,x));
if(y)insert(,y,y+x-,);
}
else{
scanf("%d%d",&x,&y);
insert(,x,x+y-,);
}
}
return ;
}