题解：P13536 [IOI 2025] 神话三峰 triples Part 1
Mirasycle
·
·
题解
本题是第一个子问题：求神话三峰的数量。
匹配是一个排序之后的结果，故我们要讨论一些相对大小关系。
不妨假设选取的神话三峰为 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_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$，这个之所以难做是因为我们无法通过其中的某个下标推到另外一个下标，所有的推导形式都至少涉及两个变量，而枚举两个变量会超时。考虑先列出所有式子，再经典处理将相同变量放到一边。
$$i+h_k=k-h_i$$
$$j+h_i=i+h_j$$
$$k-h_j=j-h_k$$
$$\to \begin{cases}
i+h_i=k-h_k
\\j-h_j=i-h_i
\\k+h_k=j+h_j
\end{cases}$$
这就很明了了吧，对于任意一个山峰 $i$ 都有两种形态 $i-h_i$ 和 $i+h_i$，这启发我们图论建模。将值看成点，在点 $i-h_i$ 和 $i+h_i$ 之间连一条边，这条边代表山峰 $i$。
于是上述三个数学式子就变成了无向图三元环的形式了！而我们要做的就是[无向图三元环计数](https://www.luogu.com.cn/problem/P1989)，给边定向之后暴力枚举即可。
最后别忘记考虑一下是否统计到重复的了。
首先不可能出现两个最大值，所以三种大的类型不会产生重复。
细节是当 $h_i=h_k$，且最大值为 $h_j$ 的时候，第三类的两种类型确实会产生重复，于是在第一类的时候特判 $h_i=h_k$ 的时候不进行统计即可。
时间复杂度 $O(n\sqrt n)$。
```cpp
#include<bits/stdc++.h>
#define pb emplace_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef vector<int> vi;
const int maxn=4e5+10;
void cmax(int &x,int y){ x=x>y?x:y; }
void cmin(int &x,int y){ x=x<y?x:y; }
int h[maxn],from[maxn],deg[maxn],n;
int p[maxn],rk[maxn],vis[maxn]; map<int,int> id;
vector<int> G[maxn],L[maxn],R[maxn];
pair<int,int> E[maxn];
bool cmp(int x,int y){ return deg[x]<deg[y]||(deg[x]==deg[y]&&x<y); }
ll count_triples(vi H){
n=H.size(); ll ans=0;
for(int i=1;i<=n;i++) h[i]=H[i-1];
//(i,j,k)
//Hi=max{Hi,Hj,Hk}
for(int i=1;i<=n;i++){
int k=i+h[i];
if(k>n) continue;
int j=i+h[k];
if(j<k&&j+h[j]==k) ans++;
if(k-h[k]!=j){
j=k-h[k];
if(i<j&&j-h[j]==i) ans++;
}
}
//Hk=max{Hi,Hj,Hk}
for(int k=1;k<=n;k++){
int i=k-h[k];
if(i<1) continue;
int j=i+h[i];
if(j<k&&j+h[j]==k) ans++;
if(k-h[i]!=j){
j=k-h[i];
if(i<j&&j-h[j]==i) ans++;
}
}
//Hj=max{Hi,Hj,Hk}
for(int i=1;i<=n;i++){
if(i+h[i]<=n) L[i+h[i]].pb(i);
if(i-h[i]>=1) R[i-h[i]].pb(i);
}
for(int i=1;i<=n;i++){
for(auto u:R[i]) vis[u]=1;
for(auto u:L[i])
if(u+h[i]<=n&&vis[u+h[i]]&&h[u+h[i]]!=h[u]) ans++;
for(auto u:R[i]) vis[u]=0;
}
int tot=0;
for(int i=1;i<=n;i++){
int h1=i+h[i];
int h2=i-h[i];
if(id.find(h1)==id.end()) id[h1]=++tot;
if(id.find(h2)==id.end()) id[h2]=++tot;
h1=id[h1]; h2=id[h2];
E[i]=mp(h1,h2); deg[h1]++; deg[h2]++;
}
for(int i=1;i<=tot;i++) p[i]=i;
sort(p+1,p+1+tot,cmp);
for(int i=1;i<=tot;i++) rk[p[i]]=i;
for(int i=1;i<=n;i++){
int u=E[i].fi,v=E[i].se;
if(rk[u]<rk[v]) G[u].pb(v);
else G[v].pb(u);
}
for(int u=1;u<=tot;u++){
for(auto v:G[u]) from[v]=u;
for(auto v:G[u])
for(auto w:G[v])
if(from[w]==u) ans++;
}
return ans;
}
```