5091：园丁大赛（gardener）
文件提交：无需freopen
内存限制：512 MB
时间限制：1.000 S
评测方式：普通裁判
金币值：
命题人：
提交：1
解决：0
题目描述
# 园丁大赛（gardener）
## 题目描述
一年一度的园丁大赛开始了。
作为一个合格的园丁，种树和挖树，是必备的基本技能。本届园丁大赛的第 $1$ 个竞技项目就是种树和挖树。
组委会准备了足够数量的树苗用于比赛，每棵树苗都有一个**唯一的编号**。
比赛在一个长方形的场地上进行，场地被划分为 $N$ 块面积大小相等的空地，编号从 $1$ 到 $N$ ，每块空地最多只能种一棵树，所有的空地在一条直线上。初始状态下，所有的空地都没有被种树。
比赛开始，裁判会依次发出 $M$ 条指令，指令共有两种：
**指令1. 种树。**
将编号为 $X_i$ 的树苗，栽到场地的某块空地上。
如果场地上没有树苗，参赛者需要将树苗种在 $1$ 号空地上。
如果场地上已经有树苗了，则需要将编号为 $X_i$ 的树苗种到距离已有树苗的**最小距离最大的**空地上，如果有多个位置满足要求，选择编号最小的空地种树苗。
**指令2. 挖树。**
将编号为 $X_i$ 的树苗，挖走。
请编程输出，对于每个**种树指令**，园丁需要种树的**空地编号**。
## 输入格式
第一行包含两个正整数 $N$ 和 $M$ ，表示场地大小和指令数量。
接下来 $M$ 行，每行有两个整数 $Op_i$ 和 $X_i$ ，表示第 $i$ 个指令的类型和需要操作的树苗的编号。
如果 $Op_i$ 的值为 $1$ ，表示要在场地上找一个空地种编号为 $X_i$ 的树苗。
如果 $Op_i$ 的值为 $2$ ，表示将场地上编号为 $X_i$ 的树苗挖走。
本题数据保证所有操作都是合法的，即：种树时，场地上一定存在空地，挖树时，场地上一定存在对应编号的树苗。
## 输出格式
对于每个**种树指令**，按题目要求输出一个空地编号，输出的空地编号之间用换行符隔开，每行一个。
## 样例
### 样例输入 1
```text
10 9
1 100
1 200
1 300
1 400
2 300
1 500
2 200
2 400
1 600
```
### 样例输出 1
```text
1
10
5
3
6
10
```
### 样例输入 2
```text
7 11
1 15
1 123
1 3
1 5
2 123
2 15
1 21
2 3
1 6
1 7
1 8
```
### 样例输出 2
```text
1
7
4
2
7
4
1
3
```
### 样例输入 3
```text
100 20
1 10
1 20
1 30
1 40
1 50
1 60
1 70
1 80
1 90
1 100
2 20
2 30
2 40
2 50
2 90
1 110
1 120
1 130
1 140
1 150
```
### 样例输出 3
```text
1
100
50
75
25
13
37
62
87
7
100
81
25
49
71
```
## 说明/提示
样例 $1$ 解释
共有 $10$ 块空地， $9$ 个指令。
- 第 $1$ 个指令为，种编号为 $100$ 的树苗，按题意种在 $1$ 号空地上。
- 第 $2$ 个指令为，种编号为 $200$ 的树苗，此时 $10$ 号空地离已有的 $1$ 号位置的树苗最远，因此种在 $10$ 号空地上。
- 第 $3$ 个指令为，种编号为 $300$ 的树苗，此时 $5$ 号空地离 $1$ 号位置的树苗的距离为 $4$ ，离 $10$ 号位置的距离为 $5$ ，最小距离为 $4$ ，分析可知，该空地满足题意要求的距已有树苗的最小距离最大的要求。虽然 $6$ 号空地也满足此要求，但 $5$ 号空地的编号更小，因此种在 $5$ 号空地上。
$\dots$
**【样例 4】**
见选手目录下的 gardener/gardener4.in 与 gardener/gardener4.ans。
该测试数据满足特殊性质 A。
**【样例 5】**
见选手目录下的 gardener/gardener5.in 与 gardener/gardener5.ans。
数据范围
对于 $100\%$ 的数据 满足 $1 \le N,M \le 200000$ ， $1 \le X_i \le 10^6$ ， $Op_i \in [1,2]$ 。
| 测试点 | $N,M$ | 特殊性质 |
|---|---|---|
| $1$ | $N=10,M=10$ | A |
| $2$ | $N=20,M=20$ | A |
| $3$ | $N=1000,M=1000$ | A |
| $4$ | $N=3000,M=3000$ | A |
| $5$ | $N=10^5,M=10^5$ | A |
| $6 \sim 11$ | $N \le 1000,M \le 1000$ | 无 |
| $13 \sim 18$ | $N \le 2 \times 10^5,M \le 2000$ | 无 |
| $19 \sim 25$ | $N \le 2 \times 10^5,M \le 2 \times 10^5$ | 无 |
特殊性质 A：对于所有的操作都满足 $Op_i=1$ ，即：只有种树的操作，没有挖树的操作。
**附件下载**
gardener.zip (564.44 KB)
---
**题目来源：** 24年7月-C组（大咖）