题目

题目描述

奶牛们最近的旅游计划，是到苏必利尔湖畔，享受那里的湖光山色，以及明媚的阳光。作为整个旅游的策划者和负责人，贝茜选择在湖边的一家著名的旅馆住宿。这个巨大的旅馆一共有$N (1 \leqslant N \leqslant 50000)$间客房，它们在同一层楼中顺次一字排开，在任何一个房间里，只需要拉开窗帘，就能见到波光粼粼的湖面。
贝茜一行，以及其他慕名而来的旅游者，都是一批批地来到旅馆的服务台，希望能订到$D_{i} (1 \leqslant D_{i} \leqslant N)$间连续的房间。
服务台的接待工作也很简单：如果存在r满足编号为$r \cdots \cdots r+D_{i}-1$的房间均空着，他就将这一批顾客安排到这些房间入住；如果没有满足条件的r，他会道歉说没有足够的空房间，请顾客们另找一家宾馆。如果有多个满足条件的r，服务员会选择其中最小的一个。旅馆中的退房服务也是批量进行的。每一个退房请求由$2$个数字$X_{i}、D_{i}$描述，表示编号为$X_{i} \cdots \cdots X_{i}+D_{i}-1 (1 \leqslant X_{i} \leqslant N-D_{i}+1)$房间中的客人全部离开。退房前，请求退掉的房间中的一些，甚至是所有，可能本来就无人入住。
而你的工作，就是写一个程序，帮服务员为旅客安排房间。你的程序一共需要处理$M (1 \leqslant M < 50000)$个按输入次序到来的住店或退房的请求。第一个请求到来前，旅店中所有房间都是空闲的。

输入输出格式

输入格式

第$1$行: $2$个用空格隔开的整数$N$和$M$
第$2 \cdots \cdots M+1$行:第$i+1$描述了第$i$个请求，如果它是一个订房请求，则用$2$个数字$1$和$D_{i}$描述，数字间用空格隔开；如果它是一个退房请求，用$3$个以空格隔开的数字$2$、$X_{i}$和$D_{i}$描述

输出格式

对于每个订房请求，输出$1$个数：如果请求能被满足，输出满足条件的最小的$r$；如果请求无法被满足，输出$0$

输入输出样例

输入样例

10 6
1 3
1 3
1 3
1 3
2 5 5
1 6

输出样例

1
4
7
0
5

题解

首先，我们先将题目简化一下，这道题需要我们实现$2$个操作：
1、订房:相当于查询是否有连续$D$个位置是空的，如果有输出最左端点
2、退房:相当于将$X$到$X+D-1$这段位置置为空
因此，我们很容易看出，这是一道支持区间查询和区间修改的线段树题。
要解决这个问题，每个节点都需要维护$4$个变量：
1、$lm$从左数最多有多少个连续的$0$
2、$rm$从右数最多有多少个连续的$0$
3、$m$整个区间最多有多少个连续的$0$
4、$sum$区间的长度
（读者：什么！？不用延迟标记（俗称$lazy$标志）吗？）
（我：…延迟标记还要写在这里吗？区间修改不是肯定需要吗?）
一开始，因为整个区间都是空的，所以我们将这些的值都赋为区间的长度。
当遇到一个查询的时候，就从根节点开始查询，为了保证最后得到的答案一定是靠左的，所以我们都先判断左边的连续$0$的个数是否大于我们需要的$D$，如果是就直接返回左端点，然后，用同样的方法判断判断中间和右边的部分。
当遇到修改的时候，就正常修改，只是在最后上传标志的时候会稍微复杂一点点，有几种情况需要判断。
最后，因为我们涉及了区间修改，所以每做一步操作都要下放标志
代码如下：

#include<iostream>
#include<cstdio>
#define l(i) t[i].l
#define r(i) t[i].r
#define m(i) t[i].m
#define lm(i) t[i].lm
#define rm(i) t[i].rm
#define sum(i) t[i].sum
#define add(i) t[i].add
using namespace std;
struct ppap 
{
  int l,r,m,lm,rm,sum,add;
}t[200010];
int n,m;
int pushup(int p)//上传标志
{
  if(sum(2*p)==m(2*p)) lm(p)=sum(2*p)+lm(2*p+1);
  else lm(p)=lm(2*p);
  if(sum(2*p+1)==m(2*p+1)) rm(p)=sum(2*p+1)+rm(2*p);
  else rm(p)=rm(2*p+1);
  m(p)=max(m(2*p),m(2*p+1));
  m(p)=max(m(p),rm(2*p)+lm(2*p+1));
}
int pushdown(int p)//下放标志
{
  int add=add(p);
  add(p)=0;
  if(l(p)==r(p)) return 0;
  if(add==1){
    lm(2*p)=rm(2*p)=m(2*p)=sum(2*p);
    lm(2*p+1)=rm(2*p+1)=m(2*p+1)=sum(2*p+1);
    add(2*p)=add(2*p+1)=1;
  }
  else if(add==2){
    lm(2*p)=rm(2*p)=m(2*p)=0;
    lm(2*p+1)=rm(2*p+1)=m(2*p+1)=0;
    add(2*p)=add(2*p+1)=2;
  }
}
int build(int p,int l,int r)//建树 
{
  l(p)=l;
  r(p)=r;
  lm(p)=rm(p)=m(p)=sum(p)=r-l+1;
  if(l==r) return 0;
  int mid=(l+r)>>1;
  build(2*p,l,mid);
  build(2*p+1,mid+1,r);
}
int change(int p,int x,int y,int f)//区间修改 
{
  pushdown(p);
  int l=l(p),r=r(p);
  if(l==x&&y==r){
    if(f==1) lm(p)=rm(p)=m(p)=sum(p);
    else lm(p)=rm(p)=m(p)=0;
    add(p)=f;
    return 0;
  }
  int mid=(l+r)>>1;
  if(mid>=y) change(2*p,x,y,f);
  else if(mid<x) change(2*p+1,x,y,f);
  else{
    change(2*p,x,mid,f);
    change(2*p+1,mid+1,y,f);
  }
  pushup(p);
}
int ask(int p,int x)//区间查询 
{
  pushdown(p);
  int l=l(p),r=r(p),mid=(l+r)>>1;
  if(l==r) return l;
  if(m(2*p)>=x) return ask(2*p,x);
  if(rm(2*p)+lm(2*p+1)>=x) return mid-rm(2*p)+1;
  return ask(2*p+1,x);
} 
int main()
{
  scanf("%d%d",&n,&m);
  build(1,1,n);
  for(int i=1;i<=m;i++){
    int f,x,y;
    scanf("%d",&f);
    if(f==1){
      scanf("%d",&x);
      if(t[1].m<x) cout<<0<<endl;
      else{
        int p=ask(1,x);
        cout<<p<<endl;
        change(1,p,p+x-1,2);
      }
    }
    else{
      scanf("%d%d",&x,&y);
      change(1,x,x+y-1,1);
    }
  }
}