2002: [Hnoi2010]Bounce 弹飞绵羊

Time Limit: 10 Sec  Memory Limit: 259 MB

Submit: 9844  Solved: 5070

[][][]

Description

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

Input

第一行包含一个整数n，表示地上有n个装置，装置的编号从0到n-1,接下来一行有n个正整数，依次为那n个装置的初始弹力系数。第三行有一个正整数m，接下来m行每行至少有两个数i、j，若i=1，你要输出从j出发被弹几次后被弹飞，若i=2则还会再输入一个正整数k，表示第j个弹力装置的系数被修改成k。对于20%的数据n,m<=10000，对于100%的数据n<=200000,m<=100000

Output

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

Sample Input

4

1 2 1 1

3

1 1

2 1 1

1 1

Sample Output

2

3

HINT

 

Source

 

 

思路：感觉这个如果说用分块的话感觉是基础题？

总体思路就是分成sqrt(n)块，然后每次都对这个块内进行更新， need表示每次走的步数，我们就只要for(j = r[i]; j >= l[i]; j--) 来逆序迭代更新就好了。

//看看会不会爆int!数组会不会少了一维！//取物问题一定要小心先手胜利的条件#include 
      
       using namespace std;#pragma comment(linker,"/STACK:102400000,102400000")#define LL long long#define ALL(a) a.begin(), a.end()#define pb push_back#define mk make_pair#define fi first#define se second#define haha printf("haha\n")const int maxn = 200000 * 2;int n, m;int step[maxn];int l[maxn], r[maxn], belong[maxn], block, num;int to[maxn], need[maxn];void build(){    block = sqrt(n); num = n / block;    if (n % block) num++;    for (int i = 1; i <= num; i++){        l[i] = (i - 1) * block + 1, r[i] = i * block;    }    for (int i = 1; i <= n; i++)        belong[i] = (i - 1) / block + 1;}void update(int be){    for (int i = l[be]; i <= r[be]; i++)        to[i] = -1, need[i] = 0;    for (int i = r[be]; i >= l[be]; i--){        int nxtpos = i + step[i];        if (nxtpos > n) nxtpos = n + 1;        if (belong[nxtpos] != be){
    //如果只走一步，且两个不是同一个块            to[i] = nxtpos; need[i] = 1;        }        else {
    //同一个块            need[i] = 1;            need[i] += need[nxtpos];            to[i] = to[nxtpos];        }    }}void query(int pos){    int cnt = 0;    while (pos <= n){        cnt += need[pos];        pos = to[pos];    }    printf("%d\n", cnt);}int main(){    cin >> n;    for (int i = 1; i <= n; i++){        scanf("%d", step + i);    }    build();    memset(to, -1, sizeof(to));    for (int i = 1; i <= num; i++){        update(i);    }/*    for (int i = 1; i <= n; i++){        printf("to[%d] = %d need[%d] = %d\n", i, to[i], i, need[i]);    }*/    cin >> m;    for (int i = 1; i <= m; i++){        int a, b, c;        scanf("%d%d", &a, &b); b++;        if (a == 2){            scanf("%d", &c);            step[b] = c;            update(belong[b]);        }        else {            query(b);        }    }    return 0;}
      

 

关键：分块的魅力在于每次不需要将序列全部更新，而是只需要更新其中的片段