变量，此题维持3个变量，假设区间l[l,r]这个区间需要保存这个区间的最大值，从l开始的最大值，以及以r结尾的最大值，对于COVER空闲为1，非空闲为0.
大概思路：对与1：先query操作找出能够容纳给定范围的第一个下标，然后update更新操作。
对于2：操作直接update操作
query操作：根据大小需要的连续房间进行qury操作，当然要先进行pushdown操作，即将当前节点cover状态赋予子代， 然后如果这个需要的房间大小如果小于其左孩子的大小
则访问孩子，另外如果是左孩子的右最大值+右孩子的左孩子最大值 大于value，很明显，就是直接左边孩子的开始处，如果都不是，则剩下的是右孩子了。。
pushdow：操作就只有一个功能判断当前节点被什么覆盖，如果COVER不为-1，则被0或者是1覆盖，然后直接将其孩子的区间就是全为覆盖值乘以其范围，如果为-1，不需要覆
操作。
update：根据更新区间操作，如果除开pushup那一部分就是一个更新区间为1或者0的操作。
pushup:一个区间（称为S): 的左最大是看左孩子的左最大，如果左孩子的左最大等于自身的区间，则S的左最大还需要包括S右孩子的左最大，同理S区间的右最大也是如此。
然后S区间的最大值就为左孩子的最大值，或者右孩子的最大值，或者是左孩子的右最大与右孩子的左最大之和。
#include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #define MAXN 55555 int lmax[MAXN<<2],rmax[MAXN<<2],mmax[MAXN<<2],cover[MAXN<<2]; void build(int l,int r,int id); void update(int left,int right,int l,int r,int id,int value); int query(int value,int l,int r,int id); void pushdown(int id,int l,int r); void pushup(int id,int l,int r); int max(int a,int b); int main() { int n,m,op,value,left,right,i; while(scanf("%d%d",&n,&m)==2) { build(1,n,1); while(m--) { scanf("%d",&op); if(op==1) { scanf("%d",&value); if(value>mmax[1]) printf("0\n"); else { left=query(value,1,n,1); printf("%d\n",left); update(left,left+value-1,1,n,1,0); } } else { scanf("%d%d",&left,&right); update(left,left+right-1,1,n,1,1); } } } } void build(int l,int r,int id) { lmax[id]=rmax[id]=mmax[id]=(r-l+1); cover[id]=-1; if(l==r) return; int mid=l+r>>1; build(l,mid,id<<1); build(mid+1,r,id<<1|1); } void update(int left,int right,int l,int r,int id,int value) { if(left<=l&&right>=r) { cover[id]=value; rmax[id]=mmax[id]=lmax[id]=(r-l+1)*value; return ; } if(l==r) return ; int mid=l+r>>1; pushdown(id,l,r); if(left<=mid) update(left,right,l,mid,id<<1,value); if(right>mid) update(left,right,mid+1,r,id<<1|1,value); pushup(id,l,r); } int query(int value,int l,int r ,int id) { if(l==r) return l; pushdown(id,l,r); int mid=l+r>>1; if(mmax[id<<1]>=value) return query(value,l,mid,id<<1); else if(rmax[id<<1]+lmax[id<<1|1]>=value) return mid-rmax[id<<1]+1; else return query(value,mid+1,r,id<<1|1); //pushup(id,l,r); } void pushdown(int id,int l,int r) { if(cover[id]!=-1) { int mid=l+r>>1; cover[id<<1]=cover[id<<1|1]=cover[id]; lmax[id<<1]=mmax[id<<1]=rmax[id<<1]=(mid-l+1)*cover[id]; lmax[id<<1|1]=rmax[id<<1|1]=mmax[id<<1|1]=(r-mid)*cover[id]; cover[id]=-1; } } void pushup(int id,int l,int r) { int mid=r+l>>1; rmax[id]=rmax[id<<1|1]+((rmax[id<<1|1]==r-mid)?rmax[id<<1]:0); lmax[id]=lmax[id<<1]+((lmax[id<<1]==mid-l+1)?lmax[id<<1|1]:0); mmax[id]=max(max(mmax[id<<1],mmax[id<<1|1]),rmax[id<<1]+lmax[id<<1|1]); } int max(int a,int b) { return a>=b?a:b; }