首页 题解

# Description

Luogu传送门

# Solution

我们直接找是否有等于 3 的等差子序列即可。

假设三个数 ai<aj<aka_i < a_j < a_k 形成了等差子序列，那么有 ai+ak=2×aja_i + a_k = 2 \times a_j，所以对于一个 aia_i 对应的 aka_k 只有一个。

因此我们对于每一个 aja_j 只需要判断一对 ai,aka_i, a_k 是否在 jj 的两边。

如何判断呢？很简单。

我们开一个权值线段树，依次往里面插入数，把相应的位置赋值为 1。

假设已经枚举到了第 jj 个数，此时 a1∼aj−1a_1 \sim a_{j - 1} 都已经在权值线段树里面了。

我们只需要判断 tj−len∼jt_{j - len \sim j} 和 tj∼j+lent_{j \sim j + len} 的 hash 值一不一样即可（tt 为权值线段树，len=min⁡(aj−1,n−aj)len = \min(a_j - 1, n - a_j) 防止越界）。

思考一下这样为什么是正确的。

假设 hash 值一样，表示所有能与 aja_j 配对的 ai,aka_i, a_k 都已经在 a1∼aj−1a_1 \sim a_{j - 1} 出现过了，自然不可能组成等差子序列。

反之自然可以。

# Code

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <bits/stdc++.h>
#define uint unsigned int

using namespace std;

namespace IO{
    inline int read(){
        int x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }

    template <typename T> inline void write(T x){
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 1e4 + 10;
int T, n;
int a[N];
uint h1[N << 2], h2[N << 2], fx[N];

#define ls rt << 1
#define rs rt << 1 | 1
#define mid ((l + r) >> 1)

inline void pushup(int l, int r, int rt){
    h1[rt] = h1[ls] * fx[r - mid] + h1[rs];
    h2[rt] = h2[rs] * fx[mid - l + 1] + h2[ls];
}

inline void update(int k, int l, int r, int rt){
    if(l > r || !rt) return;
    if(l == r) return h1[rt] = h2[rt] = 1, void();
    if(k <= mid) update(k, l, mid, ls);
    else update(k, mid + 1, r, rs);
    pushup(l, r, rt);
}

inline uint query1(int L, int R, int l, int r, int rt){
    if(L > R || !rt) return 0;
    if(L == l && r == R) return h1[rt];
    if(R <= mid) return query1(L, R, l, mid, ls);
    else if(L > mid) return query1(L, R, mid + 1, r, rs);
    else return query1(L, mid, l, mid, ls) * fx[R - mid] + query1(mid + 1, R, mid + 1, r, rs);
}

inline uint query2(int L, int R, int l, int r, int rt){
    if(L > R || !rt) return 0;
    if(L == l && r == R) return h2[rt];
    if(R <= mid) return query2(L, R, l, mid, ls);
    else if(L > mid) return query2(L, R, mid + 1, r, rs);
    else return query2(mid + 1, R, mid + 1, r, rs) * fx[mid - L + 1] + query2(L, mid, l, mid, ls);
}

int main(){
    T = read();
    fx[0] = 1;
    for(int i = 1; i < N; ++i) fx[i] = fx[i - 1] * 19;
    while(T--){
        memset(h1, 0, sizeof(h1));
        memset(h2, 0, sizeof(h2));
        n = read();
        for(int i = 1; i <= n; ++i) a[i] = read();
        bool flag = 0;
        for(int i = 1; i <= n; ++i){
            int len = min(a[i] - 1, n - a[i]);
            if(query1(a[i] - len, a[i] - 1, 1, n, 1) != query2(a[i] + 1, a[i] + len, 1, n, 1)) {flag = 1; break;}
            update(a[i], 1, n, 1);
        }
        puts(flag ? "Y" : "N");
    }
    return 0;
}
// X.K.