记录编号	582725	评测结果	AWWWWWWWWWWW
题目名称	2968.[USACO Feb08] 旅馆	最终得分	8
用户昵称	┭┮﹏┭┮	是否通过	未通过
代码语言	C++	运行时间	0.330 s
提交时间	2023-09-23 16:21:44	内存使用	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,id,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 id(x) t[x].id
    #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;
        id(x) = l(x);
    }
    else if(l(x) == r(x)){
        lm(x) = rm(x) = s(x) = 0;
        id(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)));
        if(s(x) == s(x<<1|1))id(x) = id(x<<1|1);
        else if(s(x) == rm(x<<1)+lm(x<<1|1))id(x) = r(x<<1) - rm(x<<1) + 1;
        else id(x) = id(x<<1);
    }
}
void pushdown(int x){
    if(dat(x) == 1){
        lm(x<<1) = rm(x<<1) = s(x<<1) = r(x<<1) - l(x<<1) + 1;
        id(x<<1) = l(x<<1);
        lm(x<<1|1) = rm(x<<1|1) = s(x<<1|1) = r(x<<1|1) - l(x<<1|1) + 1;
        id(x<<1|1) = l(x<<1|1); 
        dat(x<<1) = dat(x<<1|1) = dat(x);
    }
    else if(dat(x) == 0){
        lm(x<<1) = rm(x<<1) = s(x<<1) = 0;
        id(x<<1) = 0;
        lm(x<<1|1) = rm(x<<1|1) = s(x<<1|1) = 0;
        id(x<<1|1) = 0; 
        dat(x<<1) = dat(x<<1|1) = dat(x);
    }
    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 z){
    if(s(x) < z)return 0;
    int mid = l(x) + r(x) >> 1;
    pushdown(x);
    if(s(x<<1) >= z)return ask(x<<1,z);
    else return id(x);
}
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;
            id(x) = l(x);
        }
        else{
            lm(x) = rm(x) = s(x) = 0;
            id(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,y);
            printf("%d\n",ans);
            if(ans)add(1,ans,ans+y-1,0);
        }
        else{
            scanf("%d",&z);
            add(1,y,y+z-1,1);
        }
    }
    
    return 0;
    
}