题目
题目描述
奶牛们最近的旅游计划，是到苏必利尔湖畔，享受那里的湖光山色，以及明媚的阳光。作为整个旅游的策划者和负责人，贝茜选择在湖边的一家著名的旅馆住宿。这个巨大的旅馆一共有$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$，如果是就直接返回左端点，然后，用同样的方法判断判断中间和右边的部分。
当遇到修改的时候，就正常修改，只是在最后上传标志的时候会稍微复杂一点点，有几种情况需要判断。
最后，因为我们涉及了区间修改，所以每做一步操作都要下放标志
代码如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
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);
}
}
}