[HNOI2010]弹飞绵羊

题目描述

某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿着一条直线摆上n个装置，每个装置设定初始弹力系数ki，当绵羊达到第i个装置时，它会往后弹ki步，达到第i+ki个装置，若不存在第i+ki个装置，则绵羊被弹飞。绵羊想知道当它从第i个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，Lostmonkey可以修改某个弹力装置的弹力系数，任何时候弹力系数均为正整数。

输入输出格式

输入格式：

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

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

第三行有一个正整数m，

接下来m行每行至少有两个数i、j，若i=1，你要输出从j出发被弹几次后被弹飞，若i=2则还会再输入一个正整数k，表示第j个弹力装置的系数被修改成k。

输出格式：

对于每个i=1的情况，你都要输出一个需要的步数，占一行。

输入输出样例

输入样例#1： 复制

输出样例#1： 复制

2
3

说明

对于20%的数据n,m<=10000，对于100%的数据n<=200000,m<=100000

分成sqrt(n)块，设f[i]为第i个位置跳f[i]次可以跳出当前块，设to[i]为第i个位置跳出当前块到的位置；

查询直接往后跳，修改暴力修改一个区间

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
inline int read(){
    int res = 0;char ch=getchar();
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch)){res=(res<<3)+(res<<1)+(ch^48);ch=getchar();}
    return res;
}
const int N = 200005;
int n, m;
int k[N];
int f[N], to[N];
int Bl, block[N], L[N], R[N];
int main()
{
    n = read();Bl = (int)sqrt((double)n);
    for (register int i = 1 ; i <= n ; i ++){
        k[i] = read();
        block[i] = (i - 1) / Bl + 1;
        R[block[i]] = Bl * block[i], R[block[i]] = min(R[block[i]], n);
        if(!L[block[i]]) L[block[i]] = i;
    }
    //for (int i=1;i<=n;i++)printf("%d %d
", L[block[i]], R[block[i]]);
    for (register int i = n ; i >= 1 ; i --){
        if (i + k[i] > R[block[i]]){
            f[i] = 1, to[i] = i + k[i];
        }
        else{
            f[i] = f[i+k[i]] + 1, to[i] = to[i+k[i]];
        }
    }
    //for(int i=1;i<=n;i++)printf("%d
", to[i]);
    m = read();
    while (m--)
    {
        int opt = read();
        if (opt == 1){ // 询问 
            int ans = 0;
            int p = read();p += 1;
            while(p <= n){
                ans += f[p], p = to[p];
            }
            printf("%d
", ans);
        }
        else{ // 修改 
            int p = read(), kk = read();p+=1;
            k[p] = kk;
            for (register int i = R[block[p]] ; i >= L[block[p]] ; i --){
                if (i + k[i] > R[block[p]]) {
                    f[i] = 1, to[i] = i + k[i];
                }
                else {
                    f[i] = f[i+k[i]] + 1;
                    to[i] = to[i+k[i]];
                }
            }
        } 
    }
    return 0;
}