题解 P3203 【[HNOI2010]弹飞绵羊】

MaxDYF · 2019-12-14 20:38:36 · 题解

一道简单分块题。

对整个数组进行分块，块的大小取sqrt(N)，分块之后维护两个数组jump[]和step[]，分别表示跳出当前块所到达的位置与所用的步数，这两个操作都可以在线性时间内完成。

然后更改时暴力更改，由于只有单点修改，jump[]与step[]只和块内的元素有关，所以可以在O(sqrt(N))的时间内完成。

查询时直接整块整块跳，最多有O(sqrt(N))块，所以也是O(sqrt(N))的时间。

Code

#include <bits/stdc++.h>
using namespace std;
int lnk[1000000];  //原数组在块内的编号
struct node {
    int l, r;
} a[1000000];       // 保存每一个块的区间
int num[1000000];   // num[x]表示从x往后跳一步到达的位置
int jump[1000000];  // jump[x]表示在x时跳出当前块到达的位置
int step[1000000];  // step[x]表示跳出当前块所用步数
void update(int l, int r) {
    //更新当前块的jump与step值
    for (int i = r; i >= l; i--) {
        //倒序循环，用i+num[i]的值更新i
        if (i + num[i] > a[lnk[i]].r) {
            //如果一次就跳出当前块，直接更新
            jump[i] = i + num[i];
            step[i] = 1;
        } else {
            //否则继承同一块中的下一个跳到的元素
            jump[i] = jump[i + num[i]];
            step[i] = step[i + num[i]] + 1;
        }
    }
}
int block;  //每块大小
int n;
void init() {
    //分块初始化
    block = sqrt(n);
    for (int i = 0; i < n; i++)
        lnk[i] = i / block;
    for (int i = 0; i <= lnk[n - 1]; i++) {
        a[i].l = i * block;
        a[i].r = (i + 1) * block - 1;
    }
    a[lnk[n - 1]].r = n - 1;
    update(0, n - 1);  //一次更新整个序列的jump[]与step[]值
}
int ask(int x) {
    //询问弹出序列需要多少步
    int ans = 0;
    while (x < n) {
        ans += step[x];
        x = jump[x];
    }
    return ans;
}
int main() {
    ios::sync_with_stdio(NULL);
    cin.tie(NULL);
    // 输入优化，同步IO缓存并绑定cin与cout流
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> num[i];
    init();
    int q;
    cin >> q;
    while (q --> 0) {
        // q趋近于0 (滑稽)
        static int opt, x, y;
        cin >> opt >> x;
        if (opt == 1) {
            cout << ask(x) << '\n';
        } else {
            cin >> y;
            num[x] = y;
            update(a[lnk[x]].l, a[lnk[x]].r);
        }
    }
}