很有趣的一道题。双倍经验：P2757 [国家集训队] 等差子序列
要找三个数构成等差序列，一个直接的想法就是枚举中间的数 \(a_i\)，然后看它左右两边是不是有 \(a_i-k\) 和 \(a_i+k\)。这个枚举的过程已经不好再优化了，我们考虑从判断两边的值入手。
注意到题目中说 \(a\) 是一个排列，我们很自然的想到在值域上解决问题。可以从左往右扫，每次把值域上 \(a_i\) 这个位置置为 1，这样判断条件等价于判断是否有位置 \(a_i-k,a_i+k\) 值不同，直接线段树维护 hash 判断回文串即可。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf=1e18,SIZ=5e5;
const int B=1145141,I=738796363,P=1e9+7;
inline int read(){
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
int n,a[500005],pw[500005],ip[500005];
struct segtree{
#define ls p<<1
#define rs p<<1|1
#define lson l,mid,ls
#define rson mid+1,r,rs
struct Node{
int s;
}c[2000005];
void pushup(int p){
c[p].s=(c[ls].s+c[rs].s)%P;
}
void build(int l,int r,int p){
if(l==r){c[p].s=0;return;}
int mid=(l+r)>>1;
build(lson),build(rson);
pushup(p);
}
void update(int l,int r,int p,int x,int k){
if(l==r){c[p].s=k;return;}
int mid=(l+r)>>1;
if(x<=mid)update(lson,x,k);
else update(rson,x,k);
pushup(p);
}
int query(int l,int r,int p,int L,int R){
if(L>R)return 0;
if(L<=l&&r<=R)return c[p].s;
int mid=(l+r)>>1,res=0;
if(L<=mid)res=(query(lson,L,R))%P;
if(R>mid)res=(res+query(rson,L,R))%P;
return res;
}
#undef ls
#undef rs
#undef lson
#undef rson
}Tr1,Tr2;
signed main(){
pw[0]=1;
for(int i=1;i<=SIZ;i++)pw[i]=pw[i-1]*B%P;
ip[0]=1;
for(int i=1;i<=SIZ;i++)ip[i]=ip[i-1]*I%P;
int T=1;
while(T--){
n=read();for(int i=1;i<=n;i++)a[i]=read();
Tr1.build(1,n,1);Tr2.build(1,n,1);int flag=0;
for(int i=1;i<=n;i++){
Tr1.update(1,n,1,a[i],pw[n-a[i]]);Tr2.update(1,n,1,a[i],pw[a[i]-1]);
int len=min(a[i]-1,n-a[i]),l=a[i]-len,r=a[i]+len;
int h1=Tr1.query(1,n,1,l,a[i])*ip[n-a[i]]%P;
int h2=Tr2.query(1,n,1,a[i],r)*ip[a[i]-1]%P;
if(h1!=h2){flag=1;break;}
}
puts((flag?"YES":"NO"));
}
return 0;
}