等差子序列

发表于
本文字数： 5.4k | 阅读时长 ≈ 5 分钟

等差子序列

$Description$

$Soltuion$

权值线段树好题。

先知道一个东西： $a_i <= n\ \&\&\ a_i != a_j$

首先有一种很显然的 $O(n^2)$ 算法，枚举第一个与第二个，用一个桶记录，直接询问第三个元素是否存在即可。

然后考虑如何优化这个玩意，首先想到枚举第一项，然后优化找第二项与第三项的过程。

好像不太行，考虑把等差数列的式子移个项再做。

有
$$
a_j - a_i = a_k - a_j
$$
移项得
$$
2 \times a_j = a_i + a_k
$$
然后考虑枚举 $a_j$ ，询问 $a_j - x$ 与 $a_j + x$ 是否在同侧，在异侧就说明找得到这样的等差数列。

考虑用 $Hash + SegmentTree$ 实现这个过程。

我们考虑对于一个序列内有一个数，设他左边有一个 $a_i + x\ (1 <= a_i + x <= n)$ ，那么对于一个数 $a_i - x\ (1 <= a_i - x <= n)$ ，他必然在这个数的左侧或右侧，如果在右侧，那么就找到了一个等差数列，所以我们考虑在左侧寻找这么一个数。

我们用一个状态 $S$ 记录一个数是否在这段区间内出现过，出现过为 $1$ ，没出现为 $0$ 。

然后我们把这一串状态 $Hash$ 起来，从 $1 \to i - 1$ 正着做一遍， $n \to i + 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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include <bits/stdc++.h>
#include <tr1/unordered_map>
//#include"Bignum/bignum.h"
//#define lll bignum
#define lowbit(x) (x & -x)
#define debug(x) (cout << "#x = " << (x) << endl)
#define Set(x, i) memset (x, i, sizeof(x))
#define R register
#define For(i, j, k) for(R int i = (j); i <= (k); ++i)
#define foR(i, j, k) for(R int i = (j); i >= (k); --i)
#define Cross(i, j, k) for(R int i = (j); i; i = (k))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll N = 100011;
const ll INF = 5e16;

ll Q, n, a[N];
ull Base = 131, po[N], Ha[N];

namespace IO {

    inline char gc() {
        static char buf[100000], *p1 = buf, *p2 = buf;
        return (p1 == p2) && (p2 = (p1 = buf) +
            fread (buf, 1, 100000, stdin), p1 == p2)? EOF: *p1++;
    }

    #define dd ch = getchar()
    inline ll read() {
        ll x = 0; bool f = 0; char dd;
        for (; !isdigit (ch); dd) f ^= (ch == '-');
        for (; isdigit (ch); dd)  x = x * 10 + (ch ^ 48);
        return f? -x: x;
    }
    #undef dd

    inline void write( ll x ) {
        if (x < 0) putchar ('-'), x = -x;
        if (x > 9) write (x / 10); putchar (x % 10 | 48);
    }

    inline void wrn ( ll x ) { write (x); putchar (' '); }

    inline void wln ( ll x ) { write (x); putchar ('\n'); }

    inline void wlnn ( ll x, ll y ) { wrn (x), wln (y); }

}

using IO::wln;
using IO::read;

inline ull Hash ( ll l, ll r ) {
    return Ha[r] - Ha[l - 1] * po[r - l + 1];
}

namespace Segment_Tree {
    
    #define ls(x) (x << 1)
    #define rs(x) (x << 1 | 1)
    #define mid ((l + r) >> 1)
    
    struct Tree {
        ull H1, H2;
    } T[N << 2];
    
    inline void pushUp ( ll p, ll l, ll r ) {
        ll Len = (r - l + 1) >> 1;
        T[p].H1 = T[ls(p)].H1 * po[Len] + T[rs(p)].H1;
        T[p].H2 = T[rs(p)].H2 * po[r - l + 1 - Len] + T[ls(p)].H2;
    }
    
    inline void build ( ll p, ll l, ll r ) {
        if (l == r) return (void) (T[p].H1 = T[p].H2 = 0);
        build (ls(p), l, mid); build (rs(p), mid + 1, r); pushUp (p, l, r);
    }
    
    inline void Update ( ll p, ll l, ll r, ll x ) {
        if (l == r) return (void) (T[p].H1 = T[p].H2 = Base);
        if (mid >= x) Update (ls(p), l, mid, x); 
        if (mid < x)  Update (rs(p), mid + 1, r, x); pushUp (p, l, r);
    }
    
    inline ull Query ( ll p, ll l, ll r, ll ul, ll ur ) {
        if (ul > ur) return 0;
        if (l >= ul && r <= ur) return T[p].H1;
        if (mid >= ur) return Query (ls(p), l, mid, ul, ur);
        if (mid < ul)  return Query (rs(p), mid + 1, r, ul, ur);
        return Query (ls(p), l, mid, ul, mid) * 
               po[ur - mid] + Query (rs(p), mid + 1, r, mid + 1, ur);
    }
    
    inline ull query ( ll p, ll l, ll r, ll ul, ll ur ) {
        if (ul > ur) return 0;
        if (l >= ul && r <= ur) return T[p].H2;
        if (mid >= ur) return query (ls(p), l, mid, ul, ur);
        if (mid < ul)  return query (rs(p), mid + 1, r, ul, ur);
        return query (ls(p), l, mid, ul, mid) + 
               query (rs(p), mid + 1, r, mid + 1, ur) * po[mid - ul + 1];
    }
    
} // namespace Segment_Tree

using namespace Segment_Tree;

namespace Subtask1 {
    
    inline void main () {
        tr1::unordered_map <ll, ll> Vis, ID;
        For ( i, 1, n ) Vis[a[i]] = 1, ID[a[i]] = i;
        For ( i, 1, n ) For ( j, i + 1, n ) 
            if (Vis[a[j] + a[j] - a[i]] && 
                ID[a[j] + a[j] - a[i]] > j) goto Cesare;
        puts ("N"); return ; Cesare: puts ("Y");
    }
    
} // namespace Subtask1

int main() 
{
//  freopen(".in", "r", stdin);
//  freopen(".out", "w", stdout);
    po[0] = 1;
    For ( i, 1, N - 5 ) po[i] = po[i - 1] * Base;
    Q = read(); while (Q--) { 
        Set (T, 0);
        n = read();
        For ( i, 1, n ) a[i] = read();
        
        build (1, 1, n);
        
        For ( i, 1, n ) {
            ll Len = min (a[i] - 1, n - a[i]);
            Update (1, 1, n, a[i]);
            if (Query (1, 1, n, a[i] - Len, a[i] - 1) != 
                query (1, 1, n, a[i] + 1, a[i] + Len)) goto xzy;
        }
        puts ("N"); continue; xzy: puts ("Y");
    } return 0;
}

/*

*/

题目链接