旅馆

【问题描述】

$OIER$ 们最近的旅游计划，是到长春净月潭，享受那里的湖光山色，以及明

媚的阳光。你作为整个旅游的策划者和负责人，选择在潭边的一家著名的旅馆住

宿。这个巨大的旅馆一共有 $N$ ($1$ $<=$ $N$ $<=$ $50000$)间客房，它们在同一层楼中顺次

一字排开，在任何一个房间里，只需要拉开窗帘，就能见到波光粼粼的潭面。

所有的旅游者，都是一批批地来到旅馆的服务台，希望能订到 $Di$ ($1$ $<=$ $Di$ $<=$ $N$)间连续的房间。服务台的接待工作也很简单：如果存在 $r$ 满足编号为 $r$…$r$+$Di$-$1$

的房间均空着，他就将这一批顾客安排到这些房间入住；如果没有满足条件的 $r$，

他会道歉说没有足够的空房间，请顾客们另找一家宾馆。如果有多个满足条件的

$r$，服务员会选择其中最小的一个。

旅馆中的退房服务也是批量进行的。每一个退房请求由 $2$ 个数字 $Xi$、$Di$ 描

述，表示编号为 $Xi$…$Xi$+$Di$-$1$ ($1$ $<=$ $Xi$ $<=$ $N$-$Di$+$1$)房间中的客人全部离开。退房前，

请求退掉的房间中的一些，甚至是所有，可能本来就无人入住。

你的工作，就是写一个程序，帮服务员为旅客安排房间。你的程序一共需要

处理 $M$ ($1$ $<=$ $M$ $<=$ $50000$)个按输入次序到来的住店或退房的请求。第一个请求到

来前，旅店中所有房间都是空闲的。

【输入格式】

从文件 $hotel.in$ 中输入数据。

第 $1$ 行: $2$ 个用空格隔开的整数：$N$、$M$

第 $2$…$M+1$ 行: 第 $i+1$ 描述了第 $i$ 个请求，如果它是一个订房请求，则用 $2$ 个

数字 $1$、$Di$ 描述，数字间用空格隔开；如果它是一个退房请求，用 $3$ 个以空格隔

开的数字 $2$、$Xi$、$Di$ 描述。

【输出格式】

输出到文件 $hotel.out$ 中。

第 $1$…$??$行: 对于每个订房请求，输出 $1$ 个独占 $1$ 行的数字：如果请求能被

满足，输出满足条件的最小的 $r$；如果请求无法被满足，输出 $0$。

【样例输入】

$10$ $6$

$1$ $3$

$1$ $3$

$1$ $3$

$1$ $3$

$2$ $5$ $5$

$1$ $6$

【样例输出】

$1$

$4$

$7$

$0$

$5$

【数据规模与约定】

对于 $20$%的数据， $1$<=$N$<=$100$,$1$<=$M$<=$200$

对于 $100$%的数据，$1$ <= $N$ <= $50000$ ，$1$ <= $M$ <= $50000$，

数据有梯度。

该题考试的时候打了并且重构一颗线段树，顺利跑过，下面让我们来分析一下：

线段树维护区间最长连续$1$，区间前缀最长连续$1$，后缀最长连续$1$

在查询的时候看这个区间的最长长度是否>=$d$

如果>=$d$，则先看左子树是否>=$d$，若否看跨区间的是否>=$d$，若否再找右子树

再支持一下区间赋值即可。

下面贴上我丑陋的代码：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define N 50005#include
           
            #define lc (p<<1)#define rc (p<<1|1)#define mid (T[p].l+T[p].r>>1)inline long long read(){ long long ans=0,w=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-')w=-1; ch=getchar(); } while(isdigit(ch)){ ans=(ans<<3)+(ans<<1)+ch-'0'; ch=getchar(); } return ans*w;}inline void write(long long x){ if(x<0){ x=-x; putchar('-'); } if(x>9)write(x/10); putchar(x%10+'0');}struct Node{ int l,r,ms,ls,rs,lazy;}T[N<<2];inline int max(int a,int b){ return a>b?a:b;}inline void pushup(int p){ T[p].ls=T[lc].ls,T[p].rs=T[rc].rs; if(T[p].ls==T[lc].r-T[lc].l+1)T[p].ls+=T[rc].ls; if(T[p].rs==T[rc].r-T[rc].l+1)T[p].rs+=T[lc].rs; T[p].ms=max(max(T[lc].ms,T[rc].ms),T[lc].rs+T[rc].ls);}inline void pushnow(int p,int v){ T[p].ls=T[p].rs=T[p].ms=(1-v)*(T[p].r-T[p].l+1); T[p].lazy=v;}inline void pushdown(int p){ if(T[p].lazy==-1)return; pushnow(lc,T[p].lazy); pushnow(rc,T[p].lazy); T[p].lazy=-1;}inline void build(int p,int l,int r){ T[p].l=l,T[p].r=r,T[p].lazy=-1,T[p].ls=T[p].rs=T[p].ms=r-l+1; if(l==r)return; build(lc,l,mid); build(rc,mid+1,r); pushup(p);}inline void update(int p,int ql,int qr,int v){ if(ql<=T[p].l&&T[p].r<=qr){ pushnow(p,v); return; } pushdown(p); if(qr<=mid)update(lc,ql,qr,v); else if(ql>mid)update(rc,ql,qr,v); else{ update(lc,ql,mid,v); update(rc,mid+1,qr,v); } pushup(p);}inline int query(int p,int v){ if(T[p].ms
            
             =v)return query(lc,v); if(T[lc].rs+T[rc].ls>=v)return mid-T[lc].rs+1; return query(rc,v);}int n,m;int main(){ freopen("hotel.in","r",stdin); freopen("hotel.out","w",stdout); n=read(),m=read(); build(1,1,n); for(int i=1;i<=m;++i){ int op=read(); if(op==1){ int x=read(),t=query(1,x); write(t); puts(""); if(t)update(1,t,t+x-1,1); } else{ int x=read(),d=read(); update(1,x,x+d-1,0); } } return 0;}