题目描述

题目译自 2021년도 국제정보올림피아드 대표학생 선발고사 - 2차 선발고사 T4 「가로등」

沿着一条直路有 $N$ 盏路灯。第 $i$ 盏路灯的初始高度为 $A_{i}$ $(1 \leq i \leq N)$。我们计划利用这些路灯架设电线。

要在第 $i$ 盏路灯和第 $j(>i)$ 盏路灯之间架设电线，需要满足以下两个条件：

1. $A_{i}=A_{j}$（两盏路灯的高度相同）
2. 对于所有 $i<k<j$，$A_{k}<A_{i}$（两盏路灯之间的所有路灯高度都低于这两盏路灯）

根据管理员的判断，一些路灯的高度会被调整，这会改变可以架设电线的路灯对的情况。

有 $Q$ 次操作，每次操作会将第 $x$ 盏路灯的高度调整为 $h$。每次调整路灯高度后，我们需要计算可以架设电线的路灯对的数量。

实现细节

你需要实现以下函数：

vector<long long int> count_cable(vector<int> A, vector< pair<int, int> > C);

• 该函数只会被调用一次。
• 参数 $A$ 的大小为 $N$。数组 $A$ 的每个元素表示路灯的初始高度。换句话说，$A[i]=A_{i+1}$ $(0 \leq i \leq N-1)$。
• 参数 $C$ 是一个包含 $Q$ 个顺序对 $(x, h)$ 的数组，每个顺序对 $(x, h)$ 表示一次将第 $x$ 盏路灯的高度调整为 $h$ 的操作。
• 该函数返回一个大小为 $Q+1$ 的整数数组，包含初始状态下可以架设电线的路灯对的数量，以及每次高度调整后可以架设电线的路灯对的数量。

注意，提交的代码中不应包含任何输入输出操作。

样例

考虑 $A=[4,2,2,2,4,6],C=[(4,6),(6,4)]$ 的情况。

$C=[(4,6),(6,4)]$ 的意思是，第一次高度调整将第 $4$ 盏路灯的高度调整为 $6$，第二次高度调整将第 $6$ 盏路灯的高度调整为 $4$。

评测程序将调用如下函数：

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$ 个子任务外的所有子任务的条件。

数据范围与提示

对于所有输入数据，满足：

• $2 \leq N \leq 10^5$
• $1 \leq Q \leq 2.5\cdot 10^5$
• 所有路灯的高度始终是 $1$ 到 $10^{9}$ 之间的整数。
• 对于每次操作 $(x, h)$，$1 \leq x \leq N$，并且保证第 $x$ 盏路灯的高度会发生变化。也就是说，调整前第 $x$ 盏路灯的高度与 $h$ 不同。

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
1	5	$N \leq 50$；$Q \leq 100$
2	8	$N \leq 10^4$；$Q \leq 2.5\cdot 10^4$
3	11	所有路灯的高度始终不超过 $10$
4	7	所有高度调整操作都将路灯的高度降低
5	15	一旦路灯高度增加，则之后不会再降低；一旦路灯高度降低，则之后不会再增加
6	12	$Q \leq 8000$
7	16	高度发生变化的路灯总数不超过 $8000$ 盏
8	21	$N \leq 4\cdot 10^4$；$Q \leq 10^5$
9	55	无附加限制

输出格式

示例评测程序按以下格式读取输入：

• 第 $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 返回的数组

示例评测程序可能与实际评测程序不同。