题解：P13536 [IOI 2025] 神话三峰 triples Part 1

本题是第一个子问题：求神话三峰的数量。

匹配是一个排序之后的结果，故我们要讨论一些相对大小关系。

不妨假设选取的神话三峰为 $i<j<k$。

可以发现我们最关心 $\{h_i,h_j,h_k\}$ 的最大值，因为确定最大值之后就可以直接知道了 $k-i$，而如果知道了次大值或者最小值无法分辨是 $j-i$ 还是 $k-j$。所以要枚举哪个 $h$ 最大。

假设 $h_i$ 最大，我们发现枚举 $i$ 之后 $k=i+h_i$ 也能确定，再通过 $h_k$ 的信息就可以推到 $j$ 了，这样子 $i,j,k$ 都确定了，最后 check 一下 $h_j$ 是否符合要求即可。

$h_k$ 最大和上面同理，一样处理。

最难处理的是 $h_j$ 最大，因为枚举 $j$ 之后我们并不能推理出 $i,k$ 中某一个是什么。但是这里有一种情况是好做的，就是 $i+h_i=k-h_k=j$，因为我们通过 $i,k$ 都可以唯一对应 $j$，直接把满足 $i+h_i=j$ 或 $k-h_k=j$ 的下标都放在 $j$ 处做一个匹配就行了，寻找间距为 $h_j$ 的数对。枚举 $j$，给 $j$ 对应的 $k$ 打上标记，枚举 $j$ 对应的 $i$，寻找 $k=i+h_j$ 即可，由于每个数只会最多在别的数匹配的地方出现两次，所以均摊 $O(n)$。

最难做的是 $h_j$ 最大的情况下，$i+h_k=k-h_i=j$，这个之所以难做是因为我们无法通过其中的某个下标推到另外一个下标，所有的推导形式都至少涉及两个变量，而枚举两个变量会超时。考虑先列出所有式子，再经典处理将相同变量放到一边。