对于一个数 \(a_i\),如果其左侧存在一个数 \(a_j\),右侧存在一个数 \(a_k\),满足 \(a_j-a_i=a_i-a_k\),则说明 \((a_j,a_i,a_k)\) 是一个长度为 \(3\) 的等差数列子序列。
观察到 \(a_j\) 和 \(a_k\) 在 \(a_i\) 不同侧且差值相等。我们可以用一个较松的条件去约束前者,一个较紧的条件去约束后者。
从小到大枚举 \(i\),用 \(a\) 的权值线段树维护子段的哈希值,表示某个数是否在当前位置 \(i\) 的右侧。每次将 \(a_i\) 位置上的数置为 \(0\)。
如果存在任意 \(a_i\) 为中心到较近边界(\(1\) 或 \(n\))为一侧的串不是回文串,则答案为 YES
。
#include<bits/stdc++.h>
using namespace std;
#define N 300005
#define Mod 1000000007
#define Base 2
#define Min(x,y)((x)<(y)?x:y)
#define Max(x,y)((x)>(y)?x:y)
#define For(i,x,y)for(i=x;i<=(y);i++)
#define ls(p)((p)<<1)
#define rs(p)((p)<<1|1)
struct Segment_Tree
{
int hach[2],l,r;
}t[1200005];
int a[N],base[N];
int read()
{
int A;
bool K;
char C;
C=A=K=0;
while(C<‘0‘||C>‘9‘)K|=C==‘-‘,C=getchar();
while(C>‘/‘&&C<‘:‘)A=(A<<3)+(A<<1)+(C^48),C=getchar();
return(K?-A:A);
}
inline void pushup(int p)
{
t[p].hach[0]=(1LL*t[ls(p)].hach[0]*base[t[rs(p)].r-t[rs(p)].l+1]+t[rs(p)].hach[0]+Mod)%Mod;
t[p].hach[1]=(1LL*t[rs(p)].hach[1]*base[t[ls(p)].r-t[ls(p)].l+1]+t[ls(p)].hach[1]+Mod)%Mod;
}
void build(int p,int l,int r)
{
t[p].l=l;
t[p].r=r;
if(t[p].l==t[p].r)
{
t[p].hach[0]=t[p].hach[1]=1;
return;
}
int mid=(l+r)>>1;
build(ls(p),l,mid),build(rs(p),mid+1,r);
pushup(p);
}
void change(int p,int x)
{
if(t[p].l==t[p].r)
{
t[p].hach[0]=t[p].hach[1]=0;
return;
}
change((t[ls(p)].r>=x?ls(p):rs(p)),x);
pushup(p);
}
int ask(int p,int x,int y,bool z)
{
if(x<=t[p].l&&t[p].r<=y)return t[p].hach[z];
int ret=0;
if(!z)
{
if(t[ls(p)].r>=x)ret=ask(ls(p),x,y,z);
if(t[rs(p)].l<=y)ret=(1LL*ret*base[Min(y,t[rs(p)].r)-Max(t[ls(p)].r,x-1)]+ask(rs(p),x,y,z))%Mod;
}
else
{
if(t[rs(p)].l<=y)ret=ask(rs(p),x,y,z);
if(t[ls(p)].r>=x)ret=(1LL*ret*base[Min(y,t[ls(p)].r)-Max(x,t[ls(p)].l)+1]+ask(ls(p),x,y,z))%Mod;
}
return ret;
}
int main()
{
int n,i,len;
n=read();
base[0]=1;
For(i,1,n)a[i]=read(),base[i]=base[i-1]*Base%Mod;
build(1,1,n);
For(i,1,n)
{
len=Min(a[i]-1,n-a[i])+1;
if(ask(1,a[i]-len+1,a[i],0)!=ask(1,a[i],a[i]+len-1,1))puts("YES"),exit(0);
change(1,a[i]);
}
puts("NO");
return 0;
}
/*6
1 5 3 4 6 2*/