[IOI 2011] Elephants
题目背景
本题仅支持 C++ 语言提交。
9s 256MB 更改了 in 和 out 文件格式以适配洛谷且防作弊
在洛谷评测不需要包含额外头文件，但需要在代码开头加入以下内容：
extern "C"{
void init(int N, int L, int X[]);
int update(int i, int y);
}
## 题目描述
**Dancing Elephants** 是芭堤亚的一个壮观演出，$N$ 头大象在一条被称为舞台的直线上跳舞。
经过多年训练，演出中的大象能够表演许多惊人的舞蹈。演出由多幕组成。在每一幕中，恰好有一头大象表演一段可爱的舞蹈，并可能移动到不同的位置。
演出制作人想制作一本包含整场演出照片的影集。在每一幕之后，他们想拍摄观众视角下所有大象的照片。
在演出的任何时刻，多头大象可能共享同一个位置。在这种情况下，它们只是在该位置前后站立。
一台照相机可以拍摄一群大象的照片当且仅当它们的所有位置都位于某个长度为 $L$ 的线段上（包括两端点）。由于大象可能会分散在舞台上，可能需要多台照相机才能同时拍摄所有大象的快照。
例如，假设 $L=10$，大象在舞台上的位置分别为 $10$、$15$、$17$ 和 $20$。此时，一台照相机就可以为它们拍照，如下所示。（大象用三角形表示；照相机用梯形表示。）
在接下来的一幕中，位于位置 $15$ 的大象跳舞到位置 $32$。在这一幕之后，我们至少需要两台照相机才能拍下快照。
在下一幕中，位于位置 $10$ 的大象移动到位置 $7$。对于新的大象布局，我们需要三台照相机才能拍摄到所有大象。
在这个交互式任务中，你需要确定在每个 act **之后**拍摄照片所需的最**少**照相机数量。请注意，所需的照相机数量在不同幕之间可能会增加、减少或保持不变。
### 交互细节
请编写以下过程：
- 过程 `init(N,L,X)`，它接受以下参数：
- $N$ - 大象的数量。大象的编号为 $0$ 到 $N-1$。
- $L$ - 单台照相机拍摄的线段长度。你可以假设 $L$ 是一个整数，满足 $0 \le L \le 10^9$。
- $X$ - 一个一维整数数组，表示大象的初始位置。对于 $0 \le i < N$，大象 $i$ 从位置 $X[i]$ 开始。初始位置按升序排列。更精确地说，你可以假设 $0 \le X[0] \le \ldots \le X[N-1] \le 10^9$。请注意，在舞蹈过程中，大象的顺序可能会改变。
- 该过程只会被调用一次，在所有对 `update` 的调用之前。它不返回任何值。
- 过程 `update(i,y)`，它接受以下参数：
- $i$ - 在当前幕中移动的大象的编号。
- $y$ - 在当前幕之后大象 $i$ 将站立的位置。你可以假设 $y$ 是一个整数，满足 $0 \le y \le 10^9$。
- 该过程将被多次调用。每次调用对应一幕（该幕发生在之前所有幕之后）。每次调用必须返回对应幕之后拍摄所有大象照片所需的最少照相机数量。
### 交互示例
考虑 $N=4$，$L=10$，大象的初始位置为 $X=\{10,15,17,20\}$ 的情况。
首先，你的过程 `init` 将使用这些参数被调用。之后，你的过程 `update` 将为每一幕调用一次。以下是调用序列及其正确返回值的示例：
|幕编号|调用参数|返回值
|:-:|:-:|:-:
|$1$|`update(2,16)`|$1$
|$2$|`update(1,25)`|$2$
|$3$|`update(3,35)`|$2$
|$4$|`update(0,38)`|$2$
|$5$|`update(2,0)`|$3$
## 输入格式
样例 grader 按以下格式读取输入：
- 第 $1$ 行：$N$、$L$ 和 $M$，其中 $M$ 是演出中的幕数。
- 第 $2$ 行到第 $N+1$ 行：初始位置；即对于 $0 \le k < N$，第 $k+2$ 行包含 $X[k]$。
- 第 $N+2$ 行到第 $N+M+1$ 行：$M$ 幕的信息；即对于 $1 \le j \le M$，第 $N+1+j$ 行包含 $i[j]$、$y[j]$ 和 $s[j]$，用空格分隔，表示在第 $j$ 幕中，大象 $i[j]$ 移动到位置 $y[j]$，并且在该幕之后，$s[j]$ 是所需的最少照相机数量。
## 输出格式
样例 grader 输出：对于此任务，这些文件中的每一个都应精确地包含文本 `Correct.`。
## 提示
#### Subtask 1 (10 points)
- 恰好有 $N = 2$ 头大象。
- 初始时，以及每一幕之后，所有大象的位置将互不相同。
- 你的过程 `update` 将被调用至多 $100$ 次。
#### Subtask 2 (16 points)
- $1 \le N \le 100$。
- 初始时，以及每一幕之后，所有大象的位置将互不相同。
- 你的过程 `update` 将被调用至多 $100$ 次。
#### Subtask 3 (24 points)
- $1 \le N \le 5\times10^4$。
- 初始时，以及每一幕之后，所有大象的位置将互不相同。
- 你的过程 `update` 将被调用至多 $5\times10^4$ 次。
#### Subtask 4 (47 points)
- $1 \le N \le 7\times10^4$。
- 大象可能共享同一位置。
- 你的过程 `update` 将被调用至多 $7\times10^4$ 次。
#### Subtask 5 (3 points)
- $1 \le N \le 1.5\times10^5$。
- 大象可能共享同一位置。
- 你的过程 `update` 将被调用至多 $1.5\times10^5$ 次。
- 请参阅实现细节部分关于 CPU 时间限制的说明。
### 提示
- 注意：C++ 标准库 (STL) 中的集合模板可能较慢；特别是，如果使用它们，可能无法解决 subtask 5。