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

· · 题解

我只会第一问。

考虑三峰 i,j,k 中最高峰一定是 k-i。我们手动枚举最高峰的位置。

如果最高峰是 h_i=k-i，那就得到了 k。再讨论一下 h_k 是 j-i 还是 k-j 还是都可以是，就可以了。

如果最高峰是 k 是对称的。

如果最高峰是 j，有两种：一种是 h_i=j-i，h_k=k-j。这个我们可以去枚举 i，这样 j,k 唯一确定，检验一下即可。

最难的是 h_i=k-j，h_j=k-i，h_k=j-i。

把充要条件写成这样：i+h_j=j+h_i，k-h_j=j-h_k，i+h_k=k-h_i。（对 i,j,k 换元）

移项：i-h_i=j-h_j，k+h_k=j+h_j，i+h_i=k-h_k。

直接枚举 i,j 可以得到 O(n^2) 做法。

注意到 i-h_i 把所有下标分成若干等价类。合法的 i,j 属于同一个等价类。直接做看上去很困难，考虑根号分治：若干一个等价类大小不超过根号，那就枚举 i,j；否则对于这样的等价类，我们直接枚举 k，开桶 O(1) 检验是否存在 i,j。时间复杂度 O(n\sqrt n)。


#include "triples.h"
#include<bits/stdc++.h>
using namespace std;
#define MOD         998244353
#define ll          long long
#define pii         pair<int,int>
#define all(v)      v.begin(),v.end()
#define pb          push_back
#define REP(i,b,e)  for(int i=(b);i<(int)(e);++i)
#define over(x)     {cout<<(x)<<endl;return;}
#define lowbit(x)   ((x)&(-(x)))
#define cntbit(x)   __builtin_popcount(x)
#define deal(v)     sort(all(v));v.erase(unique(v.begin(),v.end()),v.end())
#define lbound(v,x) lower_bound(all(v),x)-v.begin()
vector<int>b[200005];
int cnt[400005];
long long count_triples(vector<int>a) {
    int n=a.size();
    ll ans=0;
    REP(i,0,n)if(i+a[i]<n){
        int j=i+a[i];
        if(a[j]>a[i])continue;
        if(a[i+a[j]]+a[j]==a[i])++ans;
        if(i+a[j]!=j-a[j]&&a[j-a[j]]+a[j]==a[i])++ans;
    }
    REP(i,0,n)if(i>=a[i]){
        int j=i-a[i];
        if(a[j]>a[i])continue;
        if(a[i-a[j]]+a[j]==a[i])++ans;
        if(i-a[j]!=j+a[j]&&a[j+a[j]]+a[j]==a[i])++ans;
    }
    REP(i,0,n)if(i+a[i]<n){
        int j=i+a[i];
        if(a[j]>a[i]&&i+a[j]<n){
            if(a[i+a[j]]==a[j]-a[i]&&a[i+a[j]]!=a[i])++ans;
        }
    }
    vector<int>T;
    REP(i,0,n)T.pb(i-a[i]);
    deal(T);
    REP(i,0,n)b[lbound(T,i-a[i])].pb(i);
    int B=sqrt(n);
    REP(_,0,T.size()){
        if(b[_].size()<=B){
            REP(i,0,b[_].size()){
                REP(j,i+1,b[_].size()){
                    int I=b[_][i],J=b[_][j];
                    if(J+a[I]<n&&a[J+a[I]]==J-I)++ans;
                }
            }
        }else{
            for(auto i:b[_])++cnt[i+a[i]];
            REP(i,0,n)if(i-a[i]>=0){
                ans+=cnt[i-a[i]]*cnt[i+a[i]];
            }
            for(auto i:b[_])--cnt[i+a[i]];
        }
    }
//  REP(i,0,n){
//      REP(j,i+1,n)if(i-a[i]==j-a[j]&&j+a[i]<n){
//          if(a[j+a[i]]==j-i)++ans;
//      }
//  }
    return ans;
}