专栏文章

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

IIvanZhang2009
P13536题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miojww4t
此快照首次捕获于
2025/12/02 20:25
3 个月前
此快照最后确认于
2025/12/02 20:25
3 个月前
查看原文
我只会第一问。
考虑三峰 i,j,ki,j,k 中最高峰一定是 k−ik-i。我们手动枚举最高峰的位置。
如果最高峰是 hi=k−ih_i=k-i，那就得到了 kk。再讨论一下 hkh_k 是 j−ij-i 还是 k−jk-j 还是都可以是，就可以了。
如果最高峰是 kk 是对称的。
如果最高峰是 jj，有两种：一种是 hi=j−ih_i=j-i，hk=k−jh_k=k-j。这个我们可以去枚举 ii，这样 j,kj,k 唯一确定，检验一下即可。
最难的是 hi=k−jh_i=k-j，hj=k−ih_j=k-i，hk=j−ih_k=j-i。
把充要条件写成这样：i+hj=j+hii+h_j=j+h_i，k−hj=j−hkk-h_j=j-h_k，i+hk=k−hii+h_k=k-h_i。（对 i,j,ki,j,k 换元）
移项：i−hi=j−hji-h_i=j-h_j，k+hk=j+hjk+h_k=j+h_j，i+hi=k−hki+h_i=k-h_k。
直接枚举 i,ji,j 可以得到 O(n2)O(n^2) 做法。
注意到 i−hii-h_i 把所有下标分成若干等价类。合法的 i,ji,j 属于同一个等价类。直接做看上去很困难，考虑根号分治：若干一个等价类大小不超过根号，那就枚举 i,ji,j；否则对于这样的等价类，我们直接枚举 kk，开桶 O(1)O(1) 检验是否存在 i,ji,j。时间复杂度 O(nn)O(n\sqrt n)。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...