参考样例，第一行输入n，m ，n代表有n个房间，编号为1---n，开始都为空房，m表示以下有m行操作，以下 每行先输入一个数 i ，表示一种操作：
若i为1，表示查询房间，再输入一个数x，表示在1--n 房间中找到长度为x的连续空房，输出连续x个房间中左端的房间号，尽量让这个房间号最小，若找不到长度为x的连续空房，输出0。
若i为2，表示退房，再输入两个数 x，y 代表 房间号 x---x+y-1 退房，即让房间为空。
非常好的一道线段树题
维护sum表示区间最大的连续空房间长度 le ri分表表示区间两边的连续长度 （用来维护sum用的） len 表示区间长度 更加方便
每次询问的时候先看看总的区间存不存在答案 sum【1】！！！
#include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m) #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k) #define RS(s) scanf("%s",s); #define ll long long #define pb push_back #define REP(i,N) for(int i=0;i<(N);i++) #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// #define inf 0x3f3f3f3f #define lson l,m,pos<<1 #define rson m+1,r,pos<<1|1 const int N=50000+5; int sum[N<<2],col[N<<2],le[N<<2],ri[N<<2],len[N<<2]; void up(int pos) { if(sum[pos<<1]==len[pos<<1]) le[pos]=len[pos<<1]+le[pos<<1|1]; else le[pos]=le[pos<<1]; if(sum[pos<<1|1]==len[pos<<1|1]) ri[pos]=len[pos<<1|1]+ri[pos<<1]; else ri[pos]=ri[pos<<1|1]; sum[pos]=max( ri[pos<<1]+le[pos<<1|1],max( sum[pos<<1],sum[pos<<1|1] ) ); } //1 open 2 close void down(int pos) { if(col[pos]) { col[pos<<1]=col[pos<<1|1]=col[pos]; if(col[pos]==1) { sum[pos<<1]=le[pos<<1]=ri[pos<<1]=0; sum[pos<<1|1]=le[pos<<1|1]=ri[pos<<1|1]=0; } else { sum[pos<<1]=le[pos<<1]=ri[pos<<1]=len[pos<<1]; sum[pos<<1|1]=le[pos<<1|1]=ri[pos<<1|1]=len[pos<<1|1]; } col[pos]=0; } } void build(int l,int r,int pos) { col[pos]=0; le[pos]=ri[pos]=sum[pos]=len[pos]=r-l+1; if(l==r)return; int m=(l+r)>>1; build(lson); build(rson); } void add(int L,int R,int flag,int l,int r,int pos) { if(L<=l&&r<=R) { col[pos]=flag; if(flag==1) sum[pos]=le[pos]=ri[pos]=0; else sum[pos]=le[pos]=ri[pos]=len[pos]; return ; } down(pos); int m=(l+r)>>1; if(L<=m)add(L,R,flag,lson); if(R>m)add(L,R,flag,rson); up(pos); } int query(int d,int l,int r,int pos) { if(l==r)return l; down(pos); int m=(l+r)>>1; if( sum[pos<<1]>=d )query(d,lson); else if( ri[pos<<1]+le[pos<<1|1]>=d )return m-ri[pos<<1]+1; else query(d,rson); } int main() { int n,m; RII(n,m); build(1,n,1); while(m--) { int x;RI(x); if(x==1) { int d;RI(d); if(sum[1]>=d) { int L=query(d,1,n,1); printf("%d ",L); add(L,L+d-1,1, 1,n,1); } else printf("0 "); } else { int a,b;RII(a,b); add(a,a+b-1,2,1,n,1); } } return 0; }