DDOSvoid's Blog

Luogu P3203 [HNOI2010]弹飞绵羊

发表于 更新于 分类于
本文字数： 1.8k 阅读时长 ≈ 2 分钟

题目描述

https://www.luogu.com.cn/problem/P3203

简要题意：给定一个长度为 $n$ 的序列 $a_i$ 和 $m$ 次操作，从点 $i$ 出发会被弹到 $i+a_i$，接着从 $i+a_i$ 弹到 $i+a_i+a_{i+a_i}$，直至弹到大于 $n$ 为止，每次操作修改一个 $a_i$，或者询问从 $i$​ 开始需要多少步弹飞

$n\le 2 \times 10^5,m\le 10^5$

Solution

考虑在没有修改的情况下，我们可以定义 $d[i]$ 表示 $i$ 跳到 $n$ 之外的次数，这样可以做到 $O(n)$ 预处理

但是修改之后需要重新处理这个数组，所以我们考虑分块

将 $d[i]$ 定义为跳到 $i$ 所在块的外面的次数，这样修改的话只需要 $O(\sqrt n)$

总的时间复杂度为 $O((n+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
#include <iostream>
#include <cstdio>
#include <cctype>
#include <cmath> 
#define maxn 200010
#define gc getchar
#define maxs 450
using namespace std;

int read() {
    int x = 0; char c = gc();
    while (!isdigit(c)) c = gc();
    while (isdigit(c)) x = x * 10 + c - '0', c = gc();
    return x;
} 

int n, m, a[maxn];

int blo, num, d[maxn], p[maxn], l[maxs], r[maxs], bl[maxn];  
void init_blo() {
    blo = sqrt(n); num = n / blo; if (n % blo) ++num;
    for (int i = 1; i <= n; ++i) bl[i] = (i - 1) / blo + 1; 
    for (int i = 1; i <= num; ++i) { 
        l[i] = (i - 1) * blo + 1;
        r[i] = i * blo;
    } r[num] = n; 
    for (int i = num; i; --i) 
        for (int j = r[i]; j >= l[i]; --j) {
            if (j + a[j] > r[i]) { p[j] = j + a[j]; d[j] = 1; continue; }
            d[j] = d[j + a[j]] + 1; p[j] = p[j + a[j]];
        } 
}

int query(int k) {
    int ans = 0; 
    while (k <= n) ans += d[k], k = p[k];
    return ans;
}

void update(int k, int v) {
    int bk = bl[k]; a[k] = v; 
    for (int i = r[bk]; i >= l[bk]; --i) {
        if (i + a[i] > r[bk]) { p[i] = i + a[i]; d[i] = 1; continue; }
        d[i] = d[i + a[i]] + 1; p[i] = p[i + a[i]];
    }
} 

inline void solve_1() {
    int x = read() + 1; printf("%d\n", query(x));
}

inline void solve_2() {
    int x = read() + 1, y = read();
    update(x, y);
} 

int main() { 
    n = read();
    for (int i = 1; i <= n; ++i) a[i] = read();
    init_blo(); m = read(); 
    for (int i = 1; i <= m; ++i) {
        int opt = read();
        switch (opt) {
        case 1 : solve_1(); break;
        case 2 : solve_2(); break;
        }
    }
    return 0;
}