记录编号	582728	评测结果	AAAAAAAAAAAA
题目名称	[USACO Feb08] 旅馆	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.187 s
提交时间	2023-09-23 16:46:29	内存使用	0.00 MiB

#include <bits/stdc++.h> 
using namespace std;
const int N = 5e5+10;
int n,m;
struct made{
    int l,r;
    int lm,rm,s,sum;//从左连续房间数 从右连续房间数 区间内最大连续数  区间总数 
    int dat;//延迟标记 
    #define l(x) t[x].l
    #define r(x) t[x].r
    #define lm(x) t[x].lm
    #define rm(x) t[x].rm
    #define s(x) t[x].s
    #define dat(x) t[x].dat
    #define sum(x) t[x].sum
}t[N<<2];
void pushup(int x){
    if(dat(x) == 1)lm(x) = rm(x) = s(x) = r(x) - l(x) + 1;
    else if(l(x) == r(x) || dat(x) == 0)lm(x) = rm(x) = s(x) = 0;
    else{
        if(lm(x<<1) == sum(x<<1))lm(x) = lm(x<<1) + lm(x<<1|1);
        else lm(x) = lm(x<<1);
        if(rm(x<<1|1) == sum(x<<1|1))rm(x) = rm(x<<1|1) + rm(x<<1);
        else rm(x) = rm(x<<1|1);
        s(x) = max(s(x<<1),max(s(x<<1|1),rm(x<<1)+lm(x<<1|1)));
    }//上传 
}
void pushdown(int x){
    if(dat(x) == 1){
        dat(x<<1) = dat(x<<1|1) = dat(x);
        lm(x<<1) = rm(x<<1) = s(x<<1) = r(x<<1) - l(x<<1) + 1;
        lm(x<<1|1) = rm(x<<1|1) = s(x<<1|1) = r(x<<1|1) - l(x<<1|1) + 1;
    }
    else if(dat(x) == 0){
        dat(x<<1) = dat(x<<1|1) = dat(x);
        lm(x<<1) = rm(x<<1) = s(x<<1) = 0;
        lm(x<<1|1) = rm(x<<1|1) = s(x<<1|1) = 0;
    }//延迟标记下传 
    dat(x) = -1;
}
void build(int x,int l,int r){
    l(x) = l,r(x) = r,dat(x) = 1;
    sum(x) = r-l+1; 
    if(l == r){
        pushup(x);
        return;
    }
    int mid = l + r >> 1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
    pushup(x);
}//建树初始化 
int ask(int x,int l,int r,int z){
    if(s(x) < z)return 0;
    pushdown(x);//下传延迟标记 
    int mid = l + r >> 1;
    if(s(x<<1) >= z)return ask(x<<1,l,mid,z);//左边 
    else if(rm(x<<1) + lm(x<<1|1) >= z)return mid - rm(x<<1) + 1;//中间 
    else return ask(x<<1|1,mid+1,r,z) ;//右边 
}
void add(int x,int l,int r,int z){
    if(l <= l(x) && r(x) <= r){
        dat(x) = z;
        if(z == 1)lm(x) = rm(x) = s(x) = r(x) - l(x) + 1;
        else lm(x) = rm(x) = s(x) = 0;//延迟标记 
        pushdown(x);
        return;
    }
    pushdown(x);
    int mid = l(x) + r(x) >> 1;
    if(mid >= l)add(x<<1,l,r,z);
    if(mid < r)add(x<<1|1,l,r,z);
    pushup(x);
}
int main(){
    freopen("usaco_feb08_hotel.in","r",stdin);
    freopen("usaco_feb08_hotel.out","w",stdout);
    scanf("%d%d",&n,&m);
    build(1,1,n);
    for(int i = 1;i <= m;i++){
        int x,y,z;
        scanf("%d%d",&x,&y);
        if(x == 1){
            int ans = ask(1,1,n,y);
            printf("%d\n",ans);
            if(ans)add(1,ans,ans+y-1,0);//0为被占房间 
        }
        else{
            scanf("%d",&z);
            add(1,y,y+z-1,1);//1为空房间 
        }
    }
    
    return 0;
    
}