链接

链接

思路

好久之前的考试题了吧，之前貌似抄的题解
现在理解了怕忘了,就写个题解记录一下吧，题目还是不错的
枚举中间点j
\[H_{i}-H_{j}=H_{j}-H_{k}\]
\[H_{k}+H_{i}=2*H_{j}\]
由于H是一种n的排列，所以取值就是\([1,n]\)
那就可以求出\(H_{k}\)和\(H_{k}\)的取值范围来了(处理一下边界，稳得一批)
如果取值范围内出现的数字的个数是奇数，那就说明还有一个数字在后面
这样就能A啦
还有一种是
求出取值范围内的数字的和
然后$ %2*H_{i}$
如果不是0，说明成立，参见上面式子
这里只提供第一种代码，第二种自己写吧

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=3e5+7;
int n,a[maxn];
int lowbit(int x) {return x&-x;}
struct node {
    int sum[maxn];
    void add(int x,int ad) {
        for(;x<=n;x+=lowbit(x)) sum[x]+=ad;
    }
    int query(int x) {
        int ans=0;
        for(x;x>=1;x-=lowbit(x)) ans+=sum[x];
        return ans;
    }
}tree;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    for(int i=1;i<=n;++i) {
        int L=max(1,2*a[i]-n);
        int R=min(n,2*a[i]-1);
        if((tree.query(R)-tree.query(L-1)) & 1) return puts("YES"),0;
        tree.add(a[i],1); 
    }
    puts("NO");
    return 0;
}