洛谷P3203 [HNOI2010] 弹飞绵羊题解

题目链接：P3203 [HNOI2010] 弹飞绵羊

题意：

某天，cxy 发明了一种超级弹力装置，为了在她的绵羊朋友面前显摆，她邀请小绵羊一起玩个游戏。

游戏一开始，cxy 在地上沿着一条直线摆上 $n$ 个装置，每个装置设定初始弹力系数 $k_i$，当绵羊达到第 $i$ 个装置时，它会往后弹 $k_i$ 步，达到第 $i+k_i$ 个装置，若不存在第 $i+k_i$ 个装置，则绵羊被弹飞。

绵羊想知道当它从第 $i$ 个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，cxy 可以修改某个弹力装置的弹力系数，任何时候弹力系数均为正整数。

输入格式：

第一行包含一个整数 $n$，表示地上有 $n$ 个装置，装置的编号从 $0 \sim n-1$。

接下来一行有 $n$ 个正整数，依次为那 $n$ 个装置的初始弹力系数。

第三行有一个正整数 $m$，表示操作次数。接下来 $m$ 行每行至少有两个数 $i,j$。

若 $i=1$，你要输出从编号为 $j$ 的装置出发被弹几次后被弹飞。

若 $i=2$，则会再给出一个正整数 $k$，表示编号为 $j$ 的弹力装置的系数被修改成 $k$。

输出格式：

对于每个 $i=1$ 的操作，输出一行一个整数表示答案。

数据范围：

$1\le n \le 2\times 10^5$，$1\le m \le 10^5$。

~~正经人谁写 LCT 啊~~（

可以发现，如果没有修改，那就是维护一棵树每个节点的深度。

有了修改操作后，每次修改我们看似只能暴力重构树，再暴力查询。

但是根据著名的等式

暴力 + 暴力 = 分块

考虑分块。把原序列分成 $\mathcal{O}(\frac{n}{S})$ 个块，每个块内预处理出每个节点的深度。

对于每个块内的修改，暴力重构整个块内的那棵树，这部分复杂度为 $\mathcal{O}(S)$ 。

对于查询，直接暴力跳每个块。由于块内已经预处理过了，所以这部分复杂度为 $\mathcal{O}(\frac{n}{S})$

取 $S = \sqrt{n}$ 时，总时间复杂度为 $\mathcal{O}(m \sqrt{n})$

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(1e6 + 15))

int n, m, S, a[N], to[N], dep[N], blk[N], L[N], R[N];
void build(int l, int r)
{
    Rep(i, r, l)
    {
        if(i + a[i] > R[blk[i]]) { to[i] = i + a[i]; dep[i] = 1; }
        else { to[i] = to[i + a[i]]; dep[i] = dep[i + a[i]] + 1; }
    }
}
int qry(int x)
{
    int r = 0;
    for(; x <= n; x = to[x]) r += dep[x];
    return r;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n; S = sqrt(n + 0.5); m = (n - 1) / S + 1;
    rep(i, 1, n) cin >> a[i];
    rep(i, 1, n) blk[i] = (i - 1) / S + 1;
    rep(i, 1, m) { L[i] = (i - 1) * S + 1, R[i] = i * S; }
    // rep(i, 1, m) cout << L[i] << ' ' << R[i] << '\n';
    build(1, R[m] = n); int q; cin >> q;
    while(q--)
    {
        static int op, x, y; cin >> op >> x; ++x;
        if(op == 1) cout << qry(x) << '\n';
        else { cin >> y; a[x] = y; build(L[blk[x]], R[blk[x]]); }
    }
    return 0;
}