这道题思路很巧妙。
我们从1到n处理每个数的时候同时维护好桶 (t[])。
当我们处理到 (i) 的时候，我们将 (t[a[i]]) 赋值为 (1)。
如果这时候以 (a[i]) 为中心的 (t) 极大字符串并不是一个回文串，那么就说明存在一个 (j) ,满足(t[a[i]-j]) 不等于 (t[a[i]+j])，也就是 (a[i]-j) 和 (a[i]+j) 分别在 (a[i]) 的两侧，就说明满足题目的要求。
如何判断回文串？用树状数组维护哈希就行了。
时间复杂度 (O(nlogn))
#include<iostream>
#include<cstdio>
#define ULL unsigned long long
using namespace std;
int n;
const int N=300010;
int a[N];
ULL b[N];
struct SZSZ
{
ULL tr[N];
int lowbit(int x){return x&(-x);}
void add(int pos,ULL val)
{
for(;pos<=n;pos+=lowbit(pos))tr[pos]+=val;
}
ULL ask(int pos)
{
ULL res=0;
for(;pos;pos-=lowbit(pos))res+=tr[pos];
return res;
}
}A,B;
int check(int x)
{
int len=min(x,n-x+1);
ULL u=A.ask(x)-A.ask(x-len),v=B.ask(x+len-1)-B.ask(x-1);
A.add(x,b[x]);B.add(x,b[n-x+1]);
return u*b[n-x-len+2]!=v*b[x-len+1];
}
int main()
{
cin>>n;b[0]=1;
for(int i=1;i<=n;++i)scanf("%d",&a[i]);
for(int i=1;i<=n;++i)b[i]=b[i-1]*131;
for(int i=1;i<=n;++i)
if(check(a[i]))return puts("YES")==2333;
puts("NO");
return 0;
}