题目背景

本题翻译自 2021년도 국제정보올림피아드 대표학생 선발고사 2차 선발고사 #4 가로등。

警告：滥用本题评测一次即可封号。

题目描述

一条笔直的道路上竖立着 $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$ 次。每次修改后，需立即计算当前满足条件的电线架设路灯对数，并编写程序实现此功能。

实现细节

需实现以下函数：

vector<long long int> count_cable(vector<int> A, vector< pair<int, int> > 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 返回的数组。

注意：示例评测程序与实际评测程序不同。

6 2
4 2 2 2 4 6
4 6
6 4

[3, 2, 2]

提示

约束条件

• $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$。

  调用函数：

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