给定长为 $n$ 的整数列,$m$ 次操作涉及单点修改和询问 $g(x) = min\left \{k | f^k(x) > n\right \}$,其中 $f(i) = i + a_i$ 。
$n \leq 2 \times 10^5, m \leq 2 \times 10^5, a_i \ge 0$ 。
BZOJ 2002

题解

听说正解是 LCT,但我们可以用分块水过。
考虑暴力查询,最坏情况下所有 $a_i = 1$,查询的复杂度为 $O(n)$。若不考虑修改,注意到只可能往前跳,所以可以倒着递推一遍来预处理,实现 $O(1)$ 的查询。
由于需要修改,考虑分块,对每个位置记录能跳到的第一个当前块以外的位置以及跳到此位置需要的步数,即
$$next(i) = f^{w(i)}(x)$$
$$w(i) = min\left \{k | f^k(x) > right\_bound(block(x)) \right\}$$
对每块倒着递推一遍即可计算出所有位置的 $next$ 和 $w$ 值,预处理是 $O(n)$ 的,查询可以实现 $O(\sqrt{n})$。更新时,注意到只有待修改位置所属的块中待修改位置及之前的部分的 $next$ 和 $w$ 值可能受影响,因此只要对这部分重新递推一遍,实现 $O(\sqrt{n})$,总的复杂度仅为 $O(m\sqrt{n})$。

代码

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
#include <cstdio>
#include <cmath>
#include <algorithm>
const int MAXN = 200100;
namespace S {
int n, a[MAXN], bsize, next[MAXN], w[MAXN];
inline int bmap(int x) {
return (x - 1) / bsize + 1;
}
inline int bl(int x) {
return (x - 1) * bsize + 1;
}
inline int br(int x) {
return std::min(x * bsize, n);
}
inline void init() {
bsize = ceil(sqrt(n));
int r = bmap(n), ll, rr, bi, i;
for (bi = 1; bi <= r; ++bi) {
ll = bl(bi);
rr = br(bi);
for (i = rr; i >= ll; --i) {
if (a[i] > rr)
next[i] = a[i], w[i] = 1;
else
next[i] = next[a[i]], w[i] = w[a[i]] + 1; // 因为保证了 a[i] > i
}
}
}
inline void update(int x, int v) {
int bx = bmap(x), i;
a[x] = v;
int ll = bl(bx), rr = br(bx);
for (i = x; i >= ll; --i) {
if (a[i] > rr)
next[i] = a[i], w[i] = 1;
else
next[i] = next[a[i]], w[i] = w[a[i]] + 1;
}
}
inline int query(int x) {
int res = 0;
for (; x <= n; res += w[x], x = next[x]);
return res;
}
}
int main() {
// freopen("bzoj_2002.in", "r", stdin);
// freopen("bzoj_2002.out", "w", stdout);
int m, opt, x, y, i;
scanf("%d", &S::n);
for (i = 1; i <= S::n; ++i) {
scanf("%d", &x);
S::a[i] = i + x; // 直接存储后继位置
}
S::init();
scanf("%d", &m);
for (i = 0; i < m; ++i) {
scanf("%d%d", &opt, &x);
x += 1; // 0 ~ n - 1 => 1 ~ n
if (opt == 1)
printf("%d\n", S::query(x));
else {
scanf("%d", &y);
S::update(x, x + y);
}
}
return 0;
}