JZOJ 5557 写诗

奇妙的思路……
注意到它是一个排列，所以说若枚举 j，则需要 Hi,Hk 关于 Hj 对称且 i<j<k。

于是可以考虑枚举 j，将每种高度在 j 的左侧或右侧表示出来，然后相当于判断是否为回文串。
如果不是回文串，则存在某两种高度关于 Hj 对称且在 j 的两侧。
于是线段树维护哈希值和反串哈希值即可。

代码：

#include <cstdio>
#include <algorithm>
#define ls (p << 1)
#define rs (ls | 1)
using namespace std;
const int N = 3e5;
const int P = 131;
const int mod = 998244353;
int n,a[N + 5],pw[N + 5];
struct node
{
    int sum,rev;
} seg[(N << 2) + 10];
void insert(int x,int k,int p,int tl,int tr)
{
    if(tl == tr)
    {
        seg[p].sum = seg[p].rev = k;
        return ;
    }
    int mid = tl + tr >> 1;
    x <= mid ? insert(x,k,ls,tl,mid) : insert(x,k,rs,mid + 1,tr);
    seg[p].sum = ((long long)seg[ls].sum * pw[tr - mid] % mod + seg[rs].sum) % mod;
    seg[p].rev = ((long long)seg[rs].rev * pw[mid - tl + 1] % mod + seg[ls].rev) % mod;
}
int query_sum(int l,int r,int p,int tl,int tr)
{
    if(l <= tl && tr <= r)
        return seg[p].sum;
    int mid = tl + tr >> 1;
    if(l <= mid && r > mid)
        return ((long long)query_sum(l,r,ls,tl,mid) * pw[min(r,tr) - mid] % mod + query_sum(l,r,rs,mid + 1,tr)) % mod;
    else
        return l <= mid ? query_sum(l,r,ls,tl,mid) : query_sum(l,r,rs,mid + 1,tr);
}
int query_rev(int l,int r,int p,int tl,int tr)
{
    if(l <= tl && tr <= r)
        return seg[p].rev;
    int mid = tl + tr >> 1;
    if(l <= mid && r > mid)
        return ((long long)query_rev(l,r,rs,mid + 1,tr) * pw[mid - max(l,tl) + 1] % mod + query_rev(l,r,ls,tl,mid)) % mod;
    else
        return l <= mid ? query_rev(l,r,ls,tl,mid) : query_rev(l,r,rs,mid + 1,tr);
}
int ans;
int main()
{
    freopen("poem.in","r",stdin),freopen("poem.out","w",stdout);
    scanf("%d",&n),pw[0] = 1;
    for(register int i = 1;i <= n;++i)
        scanf("%d",a + i),pw[i] = (long long)pw[i - 1] * P % mod;
    for(register int i = 1,len;i <= n;++i)
    {
        insert(a[i],1,1,1,n),len = min(a[i] - 1,n - a[i]);
        if(query_rev(a[i] - len,a[i],1,1,n) ^ query_sum(a[i],a[i] + len,1,1,n))
        {
            ans = 1;
            break;
        }
    }
    puts(ans ? "YES" : "NO");
}