P13553 [IOI 2025] 神话三峰（triples）（Part 2）

本题目前可以评测子问题 2。可在 [P13536](https://www.luogu.com.cn/problem/P13536) 评测子问题 1。

东科迪勒拉山脉是安第斯山脉跨越玻利维亚的部分。它由连续的 $N$ 座山峰组成，从 $0$ 到 $N - 1$编号。山峰 $i$（$0 \leq i < N$）的**高度** $H[i]$ 是 $1$ 到 $N - 1$ 之间的整数。 对任意两座山峰 $i$ 和 $j$（其中 $0 \le i < j < N$），它们的**距离**定义为 $d(i, j) = j - i$。根据古老的印加传说，三座山峰是**神话**三峰的条件是：它们的高度与两两之间的距离在**忽略顺序**后**匹配**。 形式化地， $(i, j, k)$ 是神话三峰的条件为： * $0 \leq i < j < k < N$， * 山峰高度 $(H[i], H[j], H[k])$ 与两两之间的距离 $(d(i,j), d(i,k), d(j,k))$ 在忽略顺序后匹配。例如，对山峰 $0, 1, 2$，其两两之间的距离是 $(1, 2, 1)$，所以山峰高度 $(H[0],H[1],H[2]) = (1,1,2)$， $(H[0],H[1],H[2]) = (1,2,1)$ 和 $(H[0],H[1],H[2]) = (2,1,1)$ 都匹配，但山峰高度 $(1,2,2)$ 则不匹配。 该问题分为两个部分，分别对应**子问题一**或者**子问题二**。你可以按任意顺序解决这些子问题。特别地，你**无需**先完成子问题一再尝试子问题二。 ### 子问题一 给定山脉的描述，你的任务是计算神话三峰的数量。 #### 实现细节 你要实现以下函数： ``` long long count_triples(std::vector H) ``` * $H$: 长度为 $N$ 的数组，表示每座山峰的高度。 * 对每个测试用例，该函数恰好被调用一次。 该函数返回一个整数 $T$，表示山脉中神话三峰的数量。 ### 子问题二 你的任务是构造包含尽量多神话三峰的山脉。该子问题包含 $6$ 个有**部分得分**的**提交答案**的子任务。 对每个子任务，你将获得两个正整数 $M$ 和 $K$，需要构造一个**最多包含** $M$ 座山峰的山脉。如果你的答案中包含**至少** $K$ 个神话三峰，你将获得该子任务的满分。否则，你的得分将与你的答案中所包含的神话三峰的数量成正比。 注意，你的答案必须是一个有效的山脉。具体来说，假设你的答案包含 $N$ 座山峰（$N$ 必须满足 $3 \leq N \leq M$）。那么，山峰 $i$ 的高度 $H[i]$（$0 \leq i < N$）必须是一个 $1$ 到 $N - 1$ 之间的整数。 #### 实现细节 有两种提交解答的方法，你可以为每个子任务选择其中一种： * **输出文件** * **函数调用** 通过**输出文件**提交解答时，请创建并提交一个格式如下的文本文件： ``` N H[0] H[1] ... H[N-1] ``` 通过**函数调用**提交解答时，你需要实现以下函数。 ``` std::vector construct_range(int M, int K) ``` * $M$: 最多允许的山峰数量。 * $K$: 期望的神话三峰数量。 * 对每个测试用例，该函数恰好被调用一次。 该函数应返回一个长度为 $N$ 的数组 $H$，表示每座山峰的高度。

子问题一和二使用相同的评测程序示例，两个子问题的区别由输入的第一行确定。 子问题一的输入格式： ``` 1 N H[0] H[1] ... H[N-1] ``` 子问题二的输入格式： ``` 2 M K ```

子问题一的输出格式： ``` T ``` 子问题二的输出格式： ``` N H[0] H[1] ... H[N-1] ``` 注意，评测程序示例的输出格式与子问题二输出文件所需的格式一致。

### 子问题 1 例子 考虑以下调用。 ``` count_triples([4, 1, 4, 3, 2, 6, 1]) ``` 该山脉中包含 $3$ 个神话三峰： * 对 $(i,j,k)=(1,3,4)$，高度 $(1,3,2)$ 与两两之间的距离 $(2,3,1)$ 匹配。 * 对 $(i,j,k)=(2,3,6)$，高度 $(4,3,1)$ 与两两之间的距离 $(1,4,3)$ 匹配。 * 对 $(i,j,k)=(3,4,6)$，高度 $(3,2,1)$ 与两两之间的距离 $(1,3,2)$ 匹配。 因此，该函数应该返回 $3$。 注意，$(0, 2, 4)$ 不构成神话三峰，因为其高度 $(4,4,2)$ 与两两之间的距离 $(2,4,2)$ 并不匹配。 ### 子问题 1 数据范围 - $3 \leq N \leq 200\,000$。 - 对每个满足 $0 \le i < N$ 的 $i$，都有 $1 \leq H[i] \leq N-1$。 ### 子任务与得分规则 子问题一总共 $70$ 分。 | 子任务 | 分数 | 额外的约束条件 | | :-----: | :----: | ---------------------- | | 1 | $8$ | $N \leq 100$ | 2 | $6$ | 对每个满足 $0 \leq i < N$ 的 $i$，都有 $H[i] \leq 10$。 | 3 | $10$ | $N \leq 2000$ | 4 | $11$ | 山峰的高度是单调不下降的。 也就是说，对每个满足 $1 \leq i < N$ 的 $i$ 都有 $H[i - 1] \leq H[i]$。 | 5 | $16$ | $N \leq 50\,000$ | 6 | $19$ | 没有额外的约束条件。 子问题二总共 $30$ 分。 每个子任务的 $M$ 和 $K$ 值是固定的，如下表所示： | 子任务 | 分数 | $M$ | $K$ | | :-----: | :---: | :--------: | :-------------: | | 7 | $5$ | $20$ | $30$ | 8 | $5$ | $500$ | $2000$ | 9 | $5$ | $5000$ | $50\,000$ | 10 | $5$ | $30\,000$ | $700\,000$ | 11 | $5$ | $100\,000$ | $2\,000\,000$ | 12 | $5$ | $200\,000$ | $12\,000\,000$ 对每个子任务，如果你的答案不构成有效的山脉，你的得分将为 $0$（在 CMS 中被报告为 `Output isn't correct`）。否则，设 $T$ 表示答案中的神话三峰数量。 则你在该子任务中的得分为： $$5 \cdot \min\left(1,\frac{T}{K}\right)$$