旅馆房间管理(Hotel G)

题目描述

对一家有 $n$ 个房间（编号为 $1 \sim n$，开始都为空房）的宾馆维护以下操作：

• 查询房间：你需要在 $1,2,\ldots,n$ 房间中找到长度为 $x$ 的连续空房。若找得到，在这 $x$ 个空房间中住上人。
• 退房：房间号 $x \sim x+y-1$ 退房，即让房间为空。

输入格式

第一行输入 $n,m$，$n$ 代表有 $n$ 个房间 $(1\leq n \leq 50,000)$，编号为 $1 \sim n$，开始都为空房，$m$ 表示以下有 $m$ 行操作 $(1\leq m \leq 50,000)$，以下每行先输入一个数 $i$，表示一种操作：

若 $i$ 为 $1$，表示查询房间，再输入一个数 $x$。

若 $i$ 为 $2$，表示退房，再输入两个数 $x,y$。

输出格式

对每个输入 $1$，输出连续 $x$ 个房间中左端的房间号，尽量让这个房间号最小，若找不到长度为 $x$ 的连续空房，输出 $0$。

样例输入 #1

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

样例输出 #1

1
4
7
0
5

数据范围

请使用高效率算法及 64 位整数（long long）避免溢出。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1600。

测试点分布

出处：原题链接