洛谷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;
}