奇妙的思路……
注意到它是一个排列，所以说若枚举 \(j\)，则需要 \(H_i,H_k\) 关于 \(H_j\) 对称且 \(i<j<k\)。
于是可以考虑枚举 \(j\)，将每种高度在 \(j\) 的左侧或右侧表示出来，然后相当于判断是否为回文串。
如果不是回文串，则存在某两种高度关于 \(H_j\) 对称且在 \(j\) 的两侧。
于是线段树维护哈希值和反串哈希值即可。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
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");
}