对于 \(a, b, \frac{a + b}{2}\) 肯定是需要固定下一些变量来考虑的。
考虑固定下 \(c = \frac{a + b}{2}\)，考虑 \(a, b\)。
那么这样的 \(a, b\) 肯定满足 \(a - c = b - c, a\not = b\)，那么以 \(c\) 为中心，\(a, b\) 就是对称的。
用 \(s_i = 0, 1\) 来表示 \(i\) 是在 \(c\) 的左边或是右边。
无解就是对于每个 \(c\)，每组关于 \(c\) 对称的 \(a, b\) 都满足 \(s_a = s_b\)。
这个条件转化一下就是令边界的关于 \(c\) 对称的对为 \(x, y(x = 1\lor y = n)\)，\(s_{x\sim y}\) 为回文串。
那么就可以用线段树维护 \(\text{Hash}\)，从左往右扫过去的时候修改对应的 \(s_i\)，然后查询一下区间正反的 \(\text{Hash}\) 进行比较。
时间复杂度 \(\mathcal{O}(n\log n)\)。
代码
#include<bits/stdc++.h>
using ull = unsigned long long;
using u128 = __uint128_t;
constexpr inline u128 qpow(u128 a, u128 b, ull p, u128 v = 1) {
while (b) {
b & 1 && ((v *= a) %= p);
(a *= a) %= p, b >>= 1;
}
return v;
}
constexpr inline bool checkpr(ull p) {
int a = __builtin_ctzll(p - 1);
ull b = p - 1 >> a;
for (ull v : {2, 325, 9375, 28178, 450775, 9780504, 1795265022}) {
u128 x = qpow(v, b, p), y = 0;
for (int c = 0; c < a; c++, x = y) {
y = x * x % p;
if (y == 1 && x != 1 && x != p - 1)
return false;
}
if (x != 1)
return false;
}
return true;
}
constexpr inline ull getpr(ull l, ull r) {
ull x = 0;
for (int v : __DATE__ __TIME__ __TIMESTAMP__) x ^= (x + v) << 13;
while (true) {
x ^= x << 13, x ^= x >> 7, x ^= x << 17;
ull y = l + x % (r - l);
if (checkpr(y)) return y;
}
return 0;
}
constexpr ull P = getpr((ull)1e3, (ull)1e5), mod = getpr((ull)1e6, (ull)1e7);
const int maxn = 3e5 + 10;
int n;
struct node_t {
ull v, b;
inline node_t(ull v_ = 0, ull b_ = 0) {
v = v_, b = b_;
}
inline node_t operator + (const node_t &a) const {
return node_t((v * a.b + a.v) % mod, (b * a.b) % mod);
}
} tr[maxn * 4][2];
inline void pushup(int k) {
tr[k][0] = tr[k << 1][0] + tr[k << 1 | 1][0];
tr[k][1] = tr[k << 1 | 1][1] + tr[k << 1][1];
}
void upd(int x, int y, int k = 1, int l = 1, int r = n) {
if (l == r)
return tr[k][0] = tr[k][1] = node_t(y, P), void();
int mid = (l + r) >> 1;
x <= mid ? upd(x, y, k << 1, l, mid) : upd(x, y, k << 1 | 1, mid + 1, r);
pushup(k);
}
node_t qry(int x, int y, int op, int k = 1, int l = 1, int r = n) {
if (x <= l && r <= y) return tr[k][op];
int mid = (l + r) >> 1;
if (y <= mid) return qry(x, y, op, k << 1, l, mid);
if (mid < x) return qry(x, y, op, k << 1 | 1, mid + 1, r);
node_t L = qry(x, y, op, k << 1, l, mid), R = qry(x, y, op, k << 1 | 1, mid + 1, r);
return ! op ? (L + R) : (R + L);
}
void build(int k = 1, int l = 1, int r = n) {
if (l == r)
return tr[k][0] = tr[k][1] = node_t(0, P), void();
int mid = (l + r) >> 1;
build(k << 1, l, mid), build(k << 1 | 1, mid + 1, r);
pushup(k);
}
int a[maxn];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
build();
for (int i = 1; i <= n; i++) {
int len = std::min(a[i] - 1, n - a[i]), l = a[i] - len, r = a[i] + len;
if (qry(l, r, 0).v != qry(l, r, 1).v)
return puts("YES"), 0;
upd(a[i], 1);
}
return puts("NO"), 0;
}