前情提要

在 Part 1 中，我们将匹配根据 $h$ 的关系分成了六种类型。其中有五种都是很好做的，第六种可以通过三元环计数来完成。

观察匹配形式，其实我们应该去尽可能构造第六种。因为前五种之所以简单是它们可以一推二，也就是三元组中确定了某一个可以推导到另一个，这是我们很不希望了，这意味着三元组的变化很小基本很固定，难以让其数量增多。

故应该从第六种入手，这个变化多。我们应该让三元环个数尽可能多。有一个很基础的想法就是我们用很少的点，然后造一堆连在它们之间的边，这样子三元组的个数就会很多。首先应该注意到点的个数不能太少，因为通过两个点之间的信息解二元一次方程可以唯一确定一组 $(i,h_i)$，也就是说不能有重边。

自己做这题的时候就止步于此，因为我觉得自己造点很考验技术，随机造点又不太靠谱的样子。于是就瞎输出了一些很小的序列的组合获得了 $78 \rm pts$。后来看了别人的代码，发现这种思路确实可行，而且正是随机！

具体来说我们随机取一些 $[0,M]$ 之间的偶数（不要太多，防止点很多导致边比较分散，但也不能太少不然的话就无法填充 $h$ 数组了），取偶数的目的是为了解方程一定有解。然后在选择偶数中枚举所有数对，通过解方程确实 $(i,h_i)$。肯定有一些 $h_i$ 到最后也没有被覆盖，我们就统一赋值为 $1$。

使用在 Part 1 中写的计数函数进行计算，多次随机，取最大的一次输出即可。

#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++;
	}
	for(int i=1;i<=n;i++) L[i].clear(),R[i].clear(); 
	for(int i=1;i<=tot;i++){
		G[i].clear(); deg[i]=0;
	} id.clear();
	return ans;
}
vi ans; int m;
void add(int x,int y){
	if(x<y) swap(x,y);
	int i=(x+y)/2,j=(x-y)/2;
	if(!ans[i]) ans[i]=j;
}
vi construct_range(int M,int K){
	ans.resize(M); int lim=2700,seed=330;
	double st=clock(); vi res; ll cur=0;
	while((clock()-st)/CLOCKS_PER_SEC<=1.8){
		mt19937 rnd(seed); vi vec;
		for(auto &z:ans) z=0;
		for(int i=0;i<=M;i+=2) vec.pb(i);
		shuffle(vec.begin(),vec.end(),rnd);
		if(vec.size()>lim) vec.resize(lim);
		for(int i=0;i<vec.size();i++)
			for(int j=0;j<i;j++) add(vec[i],vec[j]);
		for(auto &z:ans) 
			if(!z) z=1;
		int z=count_triples(ans);
		if(count_triples(ans)>cur){
			cur=z; res=ans;
		} seed++;
	}
	return res;
}

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

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

不妨假设选取的神话三峰为 $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$，这个之所以难做是因为我们无法通过其中的某个下标推到另外一个下标，所有的推导形式都至少涉及两个变量，而枚举两个变量会超时。考虑先列出所有式子，再经典处理将相同变量放到一边。

$$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$。

于是上述三个数学式子就变成了无向图三元环的形式了！而我们要做的就是无向图三元环计数，给边定向之后暴力枚举即可。

最后别忘记考虑一下是否统计到重复的了。

首先不可能出现两个最大值，所以三种大的类型不会产生重复。

细节是当 $h_i=h_k$，且最大值为 $h_j$ 的时候，第三类的两种类型确实会产生重复，于是在第一类的时候特判 $h_i=h_k$ 的时候不进行统计即可。

时间复杂度 $O(n\sqrt n)$。

#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<=n;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;
}