[USACO08FEB]Hotel G 线段树区间合并|维护最长的连续1

#include<bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ls (rt<<1)
#define rs (rt<<1|1)
using namespace std;
const int maxn=5e4+5;
int n,m;
struct tree{
    int lmx,rmx,mx,lazy,len;
}t[maxn<<2];
void push_down(int rt){
    if(!t[rt].lazy) return;
    if(t[rt].len==1){
        t[rt].lazy=0;
        return;
    }
    if(t[rt].lazy==1){
        t[ls].lmx=t[ls].rmx=t[ls].mx=t[ls].len;
        t[ls].lazy=1;
        t[rs].lmx=t[rs].rmx=t[rs].mx=t[rs].len;
        t[rs].lazy=1;
    }
    if(t[rt].lazy==2){
        t[ls].lmx=t[ls].rmx=t[ls].mx=0;
        t[ls].lazy=2;
        t[rs].lmx=t[rs].rmx=t[rs].mx=0;
        t[rs].lazy=2;
    }
    t[rt].lazy=0;
}
void push_up(int rt){
    //lmx
    if(t[ls].lmx==t[ls].len){
        t[rt].lmx=t[ls].len+t[rs].lmx;
    }
    else if(t[ls].lmx!=t[ls].len){
        t[rt].lmx=t[ls].lmx;
    }
    //rmx
    if(t[rs].rmx==t[rs].len){
        t[rt].rmx=t[rs].len+t[ls].rmx;
    }
    else if(t[rs].rmx!=t[rs].len){
        t[rt].rmx=t[rs].rmx;
    }
    //mx
    t[rt].mx=max(max(t[ls].mx,t[rs].mx),t[ls].rmx+t[rs].lmx);
}
void build(int rt,int l,int r){
    t[rt].len=r-l+1;
    t[rt].lazy=0;
    t[rt].lmx=t[rt].rmx=t[rt].mx=t[rt].len;
    if(l==r){
        return;
    }
    int mid=l+r>>1;
    build(ls,l,mid);build(rs,mid+1,r);
}
void update(int rt,int ql,int qr,int op,int l=1,int r=n){
    if(ql<=l&&r<=qr){
        if(op==1){//退房 
            t[rt].lmx=t[rt].rmx=t[rt].mx=t[rt].len;
            t[rt].lazy=1;
        }
        if(op==2){
            t[rt].lmx=t[rt].rmx=t[rt].mx=0;
            t[rt].lazy=2;
        }
        return;
    }
    push_down(rt);
    int mid=l+r>>1;
    if(ql<=mid) update(ls,ql,qr,op,l,mid);
    if(qr>mid) update(rs,ql,qr,op,mid+1,r);
    push_up(rt);
}
int query(int rt,int x,int l=1,int r=n){
    if(l==r){
        return l;
    }
    push_down(rt);
    int mid=l+r>>1,ans=0;
    if(t[ls].mx>=x) ans= query(ls,x,l,mid);
    else if(t[ls].rmx+t[rs].lmx>=x) ans= mid-t[ls].rmx+1;
    else ans= query(rs,x,mid+1,r);
    push_up(rt);
    return ans;
}
int main(){
    fastio;
    //freopen("lys.in","r",stdin);
    cin>>n>>m;
    build(1,1,n);
    for(int i=1;i<=m;i++){
        int op;cin>>op;
        if(op==1){
            int x;
            cin>>x;
            if(t[1].mx>=x) {
               int pos=query(1,x);
               cout<<pos<<endl;
               update(1,pos,pos+x-1,2);    
            }
            else cout<<0<<endl;
        }
        else {
            int x,y;
            cin>>x>>y;
            update(1,x,x+y-1,1);
        }
    }
}