「BZOJ-4373」算术天才⑨与等差数列-ZKW线段树

算术天才 ⑨ 非常喜欢和等差数列玩耍。

有一天,他给了你一个长度为 $n$ 的序列,其中第 $i$ 个数为 $a[i]$。

他想考考你,每次他会给出询问 $l, r, k$,问区间 $[l, r]$ 内的数从小到大排序后能否形成公差为 $k$ 的等差数列。
当然,他还会不断修改其中的某一项。

为了不被他鄙视,你必须要快速并正确地回答完所有问题。

注意:只有一个数的数列也是等差数列。

链接

BZOJ-4373

题解

⑨ 是最强的

⑨ 是最强的...

gcd 的做法已经烂大街了,我们来说一说 Hash 的做法。

注意到这个区间里的数其实可以看做是子串,我们只需要将其 Hash 然后与预计的等差数列比较就可以了…

朴素的想法是想字符串那样的 BKDR Hash ?

这么做显然是不优雅的,那直接求和与等差数列求和公式比较 ?

这样做直接被小数据坑 WA….

我们考虑平方后求和,而 $1^2 + 2^2 + 3^3 + \cdots n^2 = \frac {n(n + 1)(2n + 1)} {6}$,由于有 $/6$,难道还要处理逆元?

直接乘以 $6$ 自然溢出就好了….

然后我们使用 ZKW 线段树维护最小值及平方和就好了….

由于自然溢出 + ZKW 线段树常数太小,成功拿下 bzoj rk1

代码

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
/*
* created xehoth on 17-04-2017
*/
#include <bits/stdc++.h>
inline char read() {
static const int IN_LEN = 1000000;
static char buf[IN_LEN], *s, *t;
if (s == t) {
t = (s = buf) + fread(buf, 1, IN_LEN, stdin);
if (s == t) return -1;
}
return *s++;
}
template<class T>
inline void read(T &x) {
static char c;
static bool iosig;
for (c = read(), iosig = false; !isdigit(c); c = read()) {
if (c == -1) return;
if (c == '-') iosig = true;
}
for (x = 0; isdigit(c); c = read())
x = (x + (x << 2) << 1) + (c ^ '0');
if (iosig) x = -x;
}
const int OUT_LEN = 10000000;
char obuf[OUT_LEN], *oh = obuf;
inline void print(char c) {
if (oh == obuf + OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf;
*oh++ = c;
}
inline void flush() {
fwrite(obuf, 1, oh - obuf, stdout);
}
namespace SegmentTree {
const int MAXN = 300005;
struct Node {
int min, sum;
Node() {}
Node(const int min, const int sum) : min(min), sum(sum) {}
} d[524288 << 1 | 1];
int M, cnt;
inline void maintain(int k) {
d[k].min = std::min(d[k << 1].min, d[k << 1 | 1].min),
d[k].sum = d[k << 1].sum + d[k << 1 | 1].sum;
}
inline void build(const int n) {
for (M = 1; M < n + 2; M <<= 1);
for (register int i = 1; i <= n; i++)
read(d[i + M].min), d[i + M].sum = d[i + M].min * d[i + M].min * 6;
for (register int i = M - 1; i; i--) maintain(i);
}
inline void modify(int k, int v) {
d[k += M].min = v, d[k].sum = v * v * 6;
while (k >>= 1) maintain(k);
}
inline Node query(int s, int t) {
Node ans(INT_MAX, 0);
for (s = s + M - 1, t = t + M + 1; s ^ t ^ 1; s >>= 1, t >>= 1) {
(~s & 1) ? (ans.min = std::min(ans.min, d[s ^ 1].min), ans.sum += d[s ^ 1].sum) : 0;
(t & 1) ? (ans.min = std::min(ans.min, d[t ^ 1].min), ans.sum += d[t ^ 1].sum) : 0;
}
return ans;
}
inline void solve() {
register int n, m;
read(n), read(m);
build(n);
register int cmd, x, y, l, r, k, len;
Node ans;
while (m--) {
read(cmd);
if (cmd == 1) {
read(x), read(y), x ^= cnt, y ^= cnt, modify(x, y);
} else {
read(l), read(r), read(k), l ^= cnt, r ^= cnt, k ^= cnt, ans = query(l, r);
len = r - l;
if (ans.sum == ans.min * ans.min * (len + 1) * 6 +
len * (len + 1) * ans.min * k * 6 + len * (len + 1)
* (len << 1 | 1) * k * k) {
print('Y'), print('e'), print('s'), print('\n'), cnt++;
} else {
print('N'), print('o'), print('\n');
}
}
}
}
}
int main() {
SegmentTree::solve();
flush();
return 0;
}
分享到