题意
给定一个长度为 $n$ 的排列 $a_i$，问是否存在 $1 \leq i < j < k \leq n$，使得 $a_j = \dfrac{a_i + a_k}2$
题解
首先，枚举 $j$，我们只需要判断是否存在一个 $d$，使得有一个 $a_j - d$ 在 $j$ 左边，并且有一个 $a_j + d$ 在 $j$ 右边。
我们，建立一个数组 $c$，把在 $j$ 左边的数标为 $0$，而在 $j$ 右边的数标为 $1$。
这样，我们只需要判断是否存在 $d$ 使得 $c_{j - d} \neq c_{j + d}$。
考虑该命题的逆否命题：不存在 $d$ 使得 $c_{j - d} = c_{j + d}$。
相当于判断 $c$ 是否回文。
开两颗线段树，维护正区间的哈希值和逆区间的哈希值。
每次 $j$ 向右移动就相当于修改 $c_j = 0$，因为 $j$ 在 $j + 1$ 左边。对应线段树上的单点修改。
代码
template<long long mod>class Mint{using type=long long;type mad(type x,type y){return x+y>=mod?x+y-mod:x+y;}type mid(type x,type y){return x-y<0?x-y+mod:x-y;}type pow(type x,type y){type tar=1;while(y){if(y&1)tar=tar*x%mod;x=x*x%mod;y/=2;}return tar;}public:type x;Mint()=default;Mint(type x):x(x%mod){}Mint inv(Mint x){return pow(x,mod-2);}Mint operator+(Mint y){return mad(x,y.x);}Mint operator-(Mint y){return mid(x,y.x);}Mint operator*(Mint y){return x*y.x%mod;}Mint operator/(Mint y){return x*inv(y.x)%mod;}Mint operator^(Mint y){return pow(x,y.x);}operator type(){return x;}Mint operator+=(Mint y){return x=mad(x,y.x);}Mint operator-=(Mint y){return x=mid(x,y.x);}Mint operator*=(Mint y){return x=x*y.x%mod;}Mint operator/=(Mint y){return x=x*inv(y.x)%mod;}Mint operator^=(Mint y){return x=pow(x,y.x);}};
using TP = Mint<777777773>;
const TP B(19);
void STRUGGLING([[maybe_unused]] unsigned TEST_NUMBER) {
tp n; bin >> n;
vector<tp> a(n + 1), ra(n + 1, -1), rb(n + 1);
vector<TP> t1(16 * n + 1, 0), t2 = t1, Bp(n + 1, 1);
auto query1 = [&](auto& _, tp x, tp l, tp r, tp ql, tp qr) -> TP {
if (ql <= l && r <= qr) return t1[x];
tp mid = (l + r) / 2;
if (mid >= ql && mid < qr) {
return _(_, x * 2, l, mid, ql, qr) * Bp[min(qr, r) - mid] + _(_, x * 2 + 1, mid + 1, r, ql, qr);
}
if (mid >= ql) return _(_, x * 2, l, mid, ql, qr);
else return _(_, x * 2 + 1, mid + 1, r, ql, qr);
};
auto modify1 = [&](auto& _, tp x, tp l, tp r, tp m) -> void {
if (l == r) return void(t1[x] = 1);
tp mid = (l + r) / 2;
if (mid >= m) _(_, x * 2, l, mid, m);
else _(_, x * 2 + 1, mid + 1, r, m);
t1[x] = t1[x * 2] * Bp[r - mid] + t1[x * 2 + 1];
};
auto query2 = [&](auto& _, tp x, tp l, tp r, tp ql, tp qr) -> TP {
if (ql <= l && r <= qr) return t2[x];
tp mid = (l + r) / 2;
if (mid >= ql && mid < qr) {
return _(_, x * 2 + 1, mid + 1, r, ql, qr) * Bp[mid - max(l, ql) + 1] + _(_, x * 2, l, mid, ql, qr);
}
if (mid >= ql) return _(_, x * 2, l, mid, ql, qr);
else return _(_, x * 2 + 1, mid + 1, r, ql, qr);
};
auto modify2 = [&](auto& _, tp x, tp l, tp r, tp m) -> void {
if (l == r) return void(t2[x] = 1);
tp mid = (l + r) / 2;
if (mid >= m) _(_, x * 2, l, mid, m);
else _(_, x * 2 + 1, mid + 1, r, m);
t2[x] = t2[x * 2 + 1] * Bp[mid - l + 1] + t2[x * 2];
};
for (tp i = 1; i <= n; ++i) Bp[i] = Bp[i - 1] * B;
for (tp i = 1; i <= n; ++i) bin >> a[i];
for (tp j = 1; j <= n; ++j) {
modify1(modify1, 1, 1, n, a[j]);
if (tp k = min(n - a[j], a[j] - 1)) ra[j] = query1(query1, 1, 1, n, a[j] - k, a[j]);
}
for (tp j = 1; j <= n; ++j) {
modify2(modify2, 1, 1, n, a[j]);
if (tp k = min(n - a[j], a[j] - 1)) rb[j] = query2(query2, 1, 1, n, a[j], a[j] + k);
}
for (tp i = 1; i <= n; ++i) {
if (ra[i] != rb[i] && ra[i] != -1) { bin << "YES\n"; return; }
}
bin << "NO\n";
}