P11982 [KTSC 2021] 路灯 / streetlight
题目背景
本题翻译自 [2021년도 국제정보올림피아드 대표학생 선발고사](https://www.ioikorea.or.kr/archives/ioitst/2021/) 2차 선발고사 [#4 가로등](https://assets.ioikorea.or.kr/ioitst/2021/2/streetlight/streetlight_statement.pdf)。
**请注意，你不需要也不应该实现 `main` 函数。具体实现方式见【实现细节】部分。**
**警告：滥用本题评测一次即可封号。**
题目描述
一条笔直的道路上竖立着 $N$ 盏路灯。第 $i$ 盏路灯的初始高度为 $A_i$（$1 \leq i \leq N$）。
现计划利用这些路灯架设电线。
若要在第 $i$ 盏路灯和第 $j$（$> i$）盏路灯之间架设电线，必须同时满足以下两个条件：
- $A_i = A_j$（两盏路灯的高度相同）。
- 对于所有 $i < k < j$，满足 $A_k < A_i$（两盏路灯之间的所有路灯高度均低于它们）。
部分路灯的高度会根据管理者的判断进行调整，调整后可能导致电线架设条件发生变化。
“将第 $x$ 盏路灯的高度修改为 $h$”的操作共会进行 $Q$ 次。每次修改后，需立即计算当前满足条件的电线架设路灯对数，并编写程序实现此功能。
### 实现细节
需实现以下函数：
```cpp
vector count_cable(vector A, vector< pair > C)
```
- 该函数仅被调用一次。
- 参数 $A$ 的大小为 $N$，其元素表示路灯的初始高度。即 $A[i] = A_{i+1}$（$0 \leq i \leq N - 1$）。
- 参数 $C$ 是由 $Q$ 个有序对 $(x, h)$ 构成的数组，每个有序对表示一次“将第 $x$ 盏路灯的高度修改为 $h$”的操作。
- 该函数需返回一个长度为 $Q + 1$ 的整数数组，其中第一个元素为初始状态下可架设电线的路灯对数，后续元素为每次修改后的对数。
在提交的源代码中，任何位置均不得执行输入输出函数。
输入格式
示例评测程序的输入格式如下：
- 第 $1$ 行：$N \ Q$
- 第 $2$ 行：$A_1 \ A_2 \ \cdots \ A_N$
- 第 $2 + i$ 行（$1 \leq i \leq Q$）：$x_i \ h_i$
$(x_i, h_i)$ 表示第 $i$ 次修改操作。
输出格式
示例评测程序的输出格式如下：
- 第 $1$ 行：函数 `count_cable` 返回的数组。
注意：示例评测程序与实际评测程序不同。
说明/提示
### 约束条件
- $2 \leq N \leq 100\,000$
- $1 \leq Q \leq 250\,000$
- 所有路灯高度均为 $1$ 至 $10^9$ 之间的整数。
- 在修改第 $x$ 盏路灯高度为 $h$ 的操作中，保证 $1 \leq x \leq N$ 且修改前该路灯高度不等于 $h$。
### 子任务
1. （$5$ 分）
- $N \leq 50$
- $Q \leq 100$
2. （$8$ 分）
- $N \leq 10\,000$
- $Q \leq 25\,000$
3. （$11$ 分）
- 所有路灯高度不超过 $10$。
4. （$7$ 分）
- 所有修改操作均降低路灯高度。
5. （$15$ 分）
- 若某路灯高度曾被增加，则后续不会降低。
- 若某路灯高度曾被降低，则后续不会增加。
6. （$12$ 分）
- $Q \leq 8\,000$
7. （$16$ 分）
- 高度被修改过的路灯总数不超过 $8\,000$ 盏。
8. （$21$ 分）
- $N \leq 40\,000$
- $Q \leq 100\,000$
9. （$55$ 分）
- 无额外约束。
### 评分标准
各子任务的得分为该子任务所有测试数据得分的最小值。
### 示例
- 设 $A = [4, 2, 2, 2, 4, 6]$，$C = [(4, 6), (6, 4)]$。
$C = [(4, 6), (6, 4)]$ 表示第一次操作将第 $4$ 盏路灯高度改为 $6$，第二次操作将第 $6$ 盏路灯高度改为 $4$。
调用函数：
```cpp
count_cable([4,2,2,2,4,6], [(4,6),(6,4)])
```
下图展示了初始状态下 $6$ 盏路灯间可架设的 $3$ 条电线：
下图展示第一次修改后（第 $4$ 盏高度改为 $6$）可架设的 $2$ 条电线：
下图展示第二次修改后（第 $6$ 盏高度改为 $4$）可架设的 $2$ 条电线：
函数 `count_cable` 应返回 `[3, 2, 2]`。
此示例满足除子任务 $4$ 外所有子任务的条件。