这道题的意思是：N个房间(1-n)，进行M次操作，1 x :代表第一种操作：向连续的x房间里面住人，如果能住返回第一个房间的号码（如果有多重解，返回最小值），如果不能住，则输出0.
2 X Y：代表第二种操作，将x,x+1...x+y-1的房间清空。
还是看了题解搞定的一道。。。
总体思路：定义 lmax,rmax,amax,代表分别代表最左端最大连续空着的房间数，最右端最大连续空着的房间数，总的最大空着的连续房间数。lazy表示这段区间是否进行过了pushdown操作，-1表示进行过了，0,1分别表示现在这段区间的状态：空还是满的，update操作中找到对应区间后，把这个区间进行lazy标记，然后再pushup，更新之前的结点。query操作，先在结点的左儿子的asum找，如果符合了，进入左儿子query，然后在中间的部分找，如果符合了直接返回值：m-tree[rt<<1].rmax+1。最后在右儿子里面找。每一次找都要先pushdown，把lazy标记去掉，并且向下pushdwn。
下面是ac代码：
#include#include #include #include #include #include #include #include #define lson rt<<1,l,m#define rson rt<<1|1,m+1,rusing namespace std;const int maxn = 50005;struct Node{ int l,r; int lmax,rmax,amax; int lazy;}tree[8*maxn];int pos;void PushDown(int rt){ int l=tree[rt].l; int r=tree[rt].r; int m=(r+l)>>1; if(tree[rt].lazy!=-1) { tree[rt<<1].lazy=tree[rt<<1|1].lazy=tree[rt].lazy; tree[rt<<1].lmax=tree[rt<<1].rmax=tree[rt<<1].amax=(tree[rt].lazy) ? 0 : (m-l+1); tree[rt<<1|1].lmax=tree[rt<<1|1].rmax=tree[rt<<1|1].amax=(tree[rt].lazy) ? 0:(r-m); tree[rt].lazy=-1; }}void PushUp(int rt){ int ll=tree[rt<<1].r-tree[rt<<1].l+1,rr=tree[rt<<1|1].r-tree[rt<<1|1].l+1; tree[rt].lmax=tree[rt<<1].lmax; tree[rt].rmax=tree[rt<<1|1].rmax; if(ll==tree[rt<<1].lmax) tree[rt].lmax+=tree[rt<<1|1].lmax; if(rr==tree[rt<<1|1].rmax) tree[rt].rmax+=tree[rt<<1].rmax; tree[rt].amax=max(max(tree[rt<<1].amax,tree[rt<<1|1].amax),(tree[rt<<1].rmax+tree[rt<<1|1].lmax));}void Build(int rt,int l,int r){ tree[rt].l=l; tree[rt].r=r; tree[rt].lmax=tree[rt].rmax=tree[rt].amax=(r-l+1); tree[rt].lazy=-1; if(l==r) return; int m=(l+r)>>1; Build(lson); Build(rson);}void query(int rt,int v){ int l=tree[rt].l; int r=tree[rt].r; int m=(l+r)>>1; if(l==r) { pos=l; return; } PushDown(rt); if(tree[rt<<1].amax>=v) query(rt<<1,v); else if(tree[rt<<1].rmax+tree[rt<<1|1].lmax>=v) { pos=m-tree[rt<<1].rmax+1; return; } else query(rt<<1|1,v);}void update(int rt,int c,int s,int e){ int l=tree[rt].l; int r=tree[rt].r; int m=(l+r)>>1; if(l==s && r==e) { tree[rt].lmax=tree[rt].rmax=tree[rt].amax= c ? 0:(r-l+1); tree[rt].lazy=c; return; } PushDown(rt); if(e<=m) update(rt<<1,c,s,e); else if(s>m) update(rt<<1|1,c,s,e); else { update(rt<<1,c,s,m); update(rt<<1|1,c,m+1,e); } PushUp(rt);}int main(){ int n,m; while(scanf("%d%d",&n,&m)!=EOF) { Build(1,1,n); int k,x,y; while(m--) { scanf("%d",&k); if(k==1) { scanf("%d",&x); if(tree[1].amax