【弹飞绵羊_HNOI2010】

题目大意

一共有\(n\)各装置，从\(0~n-1\)编号，第\(i\)个装置有一个系数\(A_i\)，表示这个装置能将绵羊向后弹一次，到达第\(i+A_i \text{ }\)个装置，如果不存在第\(i+A_i\text{ }\)个装置，则绵羊被弹飞。现在有\(m\)个操作，询问当绵羊站在第\(i\)个装置多少次被弹飞或者修改某个装置的系数。

分析一下

• 啊LCT是什么\(\cdots\)，啊我不会啊\(\cdots\)
• 恩，可以单点修改，暴力求解。
• 诶怎么跟某种数据结构那么像？
• 用块状数组来维护一下，就能使修改与求解的时间均衡了。

流程

• 给\(n\)个装置分块，每个块的大小为\(\sqrt n\)。预处理出每个装置所在块的编号，每个块的边界。
• 用两个大小为\(n\)的数组记录从第\(i\)个装置出发，跳到下一个块的次数，以及跳到下一个块的哪个位置。
• 先给\(n\)个装置全部\(DP\)一遍，求出两个数组（\(DP\)流程见代码）。当要查询时，一个指针从当前指针开始使劲往下一个块弹，用一个变量记录弹到下一个块的次数。
• 修改的时候只需要在原数组中修改系数，然后在整个块中用\(DP\)维护一遍，因为当前块并不影响前面的和后面的块，反正查询时也是一个快一个块找的。
• 时间复杂度\(O(m \cdot \sqrt n)\)
• \(A\)啦！

代码君

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cctype>

using namespace std;

inline int read() {
    int ch = getchar(), x = 0, op = 1;
    while (!isdigit(ch)) {if (ch == ‘-‘) op = -1; ch = getchar();}
    while (isdigit(ch)) {x = (x << 1) + (x << 3) + ch - ‘0‘; ch = getchar();}
    return x * op;
}

int n, m, block;
int ar[200005], bl[200005], tot[200005], to[200005]; //tot[i]表示在第i个装置上弹几次弹出当前块。 
struct BLOCK {                                       //to[i]表示弹出当前块后到达哪个装置。 
    int l, r;
} base[505];

void DP(int L, int R) {
    for (int i = R; i >= L; i--)
        if (i + ar[i] > base[bl[i]].r)
            tot[i] = 1, to[i] = i + ar[i]; //如果能弹出当前块就直接赋值。 
        else tot[i] = tot[i + ar[i]] + 1, to[i] = to[i + ar[i]]; //不能的话就把能弹到的装置上的信息赋给它。 
}                                                                //能弹到的装置保证已经求出了信息。 

int main() {
    n = read(), block = sqrt(n); //block表示每个快的大小。 
    for (int i = 1; i <= n; i++)
        ar[i] = read();
    for (int i = 1; i <= n; i++)
        bl[i] = (i - 1) / block + 1; //预处理出每个装置所在的块的编号。 
    for (int i = 1; i <= bl[n]; i++)
        base[i].l = (i - 1) * block + 1, base[i].r = min(i * block, n); //预处理出每个块的左右边界。 
    
    DP(1, n); //先求出两个数组。 
    m = read();
    while (m--) {
        int choice = read(), x = read() + 1, y;
        if (choice == 1) {
            int ans = tot[x];
            for (int X = to[x]; X <= n; X = to[X])
                ans += tot[X]; //当前块到最后一个块进行扫描。 
            printf("%d\n", ans);
        } else {
            y = read();
            ar[x] = y;
            DP(base[bl[x]].l, base[bl[x]].r); // 维护当前块。 
        }
    }
    return 0;
}

【弹飞绵羊_HNOI2010】

原文：https://www.cnblogs.com/JackHomes/p/9459582.html