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

很厉害的题。

分类讨论 $(i,j,k)$（$i<j<k$）和相对高度之间的对应关系：

• $i$ 的高度最高。那么此时 $i$ 和距离她最远的结点 $k$ 之间的距离 $|k-i|$ 一定能对应上 $a_i$（因为 $|k-i|>\max(|j-i|,|k-j|)$ 而 $a_i\ge\max(h_j,h_k)$），那么可以确定 $k=i+h_i$，然后 $j$ 的位置直接枚举剩余的两种对应关系判断是否可行即可。
• $k$ 的高度最高，和上一类情况处理方式相同。
• $j$ 的高度最高，此时继续分类讨论：
  • 对应关系形如 $h_i=|j-i|,h_k=|k-j|$ 即 $i+h_i=k-h_k=j$，那么开桶存储 $i+h_i$ 然后随便计数就能做到线性 / 单 log。
  • 对应关系形如 $h_i=|k-j|,h_k=|j-i|$ 即 $i+h_k=k-h_i=j$，此时把三个关系式都列出来然后把相同参数的放在一边，得到：$i+h_i=k-h_k,j-h_j=i-h_i,j+h_j=k+h_k$ 然后计数满足这些条件的三元组 $(i,j,k)$，经典套路考虑建图，将 $i-h_i$ 和 $i+h_i$ 连一条双向边，这样问题就转化为在新图中对三元环计数，可以做到 $O(n\sqrt n)$。

于是这个题就做完了，总时间复杂度为 $O(n\sqrt n)$ 可以通过。