#212067. [KTSC 2021] 路灯 / streetlight

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

请注意，你不需要也不应该实现 main 函数。具体实现方式见【实现细节】部分。

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

一条笔直的道路上竖立着 盏路灯。第 盏路灯的初始高度为 （）。

现计划利用这些路灯架设电线。

若要在第 盏路灯和第 （）盏路灯之间架设电线，必须同时满足以下两个条件：

• （两盏路灯的高度相同）。

• 对于所有 ，满足 （两盏路灯之间的所有路灯高度均低于它们）。

部分路灯的高度会根据管理者的判断进行调整，调整后可能导致电线架设条件发生变化。

“将第 盏路灯的高度修改为 ”的操作共会进行 次。每次修改后，需立即计算当前满足条件的电线架设路灯对数，并编写程序实现此功能。

实现细节

需实现以下函数：

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

• 该函数仅被调用一次。
• 参数 的大小为 ，其元素表示路灯的初始高度。即 （）。
• 参数 是由 个有序对 构成的数组，每个有序对表示一次“将第 盏路灯的高度修改为 ”的操作。
• 该函数需返回一个长度为 的整数数组，其中第一个元素为初始状态下可架设电线的路灯对数，后续元素为每次修改后的对数。

在提交的源代码中，任何位置均不得执行输入输出函数。

示例评测程序的输入格式如下：

• 第 行：
• 第 行：
• 第 行（）：

表示第 次修改操作。

示例评测程序的输出格式如下：

• 第 行：函数 count_cable 返回的数组。

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

样例输入 1

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

样例输出 1

[3, 2, 2]

约束条件

• 所有路灯高度均为 至 之间的整数。
• 在修改第 盏路灯高度为 的操作中，保证 且修改前该路灯高度不等于 。

子任务

1. （ 分）
2. （ 分）
3. （ 分）
   • 所有路灯高度不超过 。
4. （ 分）
   • 所有修改操作均降低路灯高度。
5. （ 分）
   • 若某路灯高度曾被增加，则后续不会降低。
   • 若某路灯高度曾被降低，则后续不会增加。
6. （ 分）
7. （ 分）
   • 高度被修改过的路灯总数不超过 盏。
8. （ 分）
9. （ 分）
   • 无额外约束。

评分标准

各子任务的得分为该子任务所有测试数据得分的最小值。

示例

• 设 ，。

  表示第一次操作将第 盏路灯高度改为 ，第二次操作将第 盏路灯高度改为 。

  调用函数：

  count_cable([4,2,2,2,4,6], [(4,6),(6,4)])
  

  下图展示了初始状态下 盏路灯间可架设的 条电线：

  

  下图展示第一次修改后（第 盏高度改为 ）可架设的 条电线：

  

  下图展示第二次修改后（第 盏高度改为 ）可架设的 条电线：

  

  函数 count_cable 应返回 [3, 2, 2]。

  此示例满足除子任务 外所有子任务的条件。