【BZOJ】2002: [Hnoi2010]Bounce 弹飞绵羊

2002: [Hnoi2010]Bounce 弹飞绵羊

Time Limit: 10 Sec Memory Limit: 259 MB
Submit: 14802 Solved: 7507
[Submit][Status][Discuss]

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

[Submit][Status][Discuss]

HOME Back

网上题解都是LCT？？QAQ明明就是分块暴力跳嘛！是随手a的第一道分块叻！要注意的就是修改操作从后往前更新就是$O(sqrt{n})$，正着就$O(sqrt{n}*sqrt{n})$叻QAQ，还有最后一块可能并没有占满整个块，导致跳出$n$跳不出块就会死循环，所以一定要取$min$！！

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;

int n, m, blo;
int a[200005], cnt[200005], jum[200005], bl[200005];

void init ( int x ) {
    int pos = x; cnt[x] = 0;
    while ( pos <= min ( bl[x] * blo, n ) ) {
        cnt[x] ++;
        pos += a[pos];
    }
    jum[x] = pos;
}

int query ( int x ) {
    int pos = x, ans = 0;
    while ( pos <= n ) ans += cnt[pos], pos = jum[pos];
    return ans;
}

void modify ( int x, int y ) {
    int pos = x; cnt[x] = 0; a[x] = y;
    for ( int i = x; i >= blo * ( bl[x] - 1 ) + 1; i -- ) {
        if ( i + a[i] <= min ( blo * bl[x], n ) )
            cnt[i] = cnt[i+a[i]] + 1, jum[i] = jum[i+a[i]];
        else cnt[i] = 1, jum[i] = i + a[i];
    }
}

int main ( ) {
    scanf ( "%d", &n );
    for ( int i = 1; i <= n; i ++ ) scanf ( "%d", &a[i] );
    blo = sqrt ( n );
    for ( int i = 1; i <= n; i ++ ) bl[i] = ( i + blo - 1 ) / blo;
    for ( int i = 1; i <= n; i ++ ) init ( i );
    scanf ( "%d", &m );
    for ( int i = 1; i <= m; i ++ ) {
        int opt;
        scanf ( "%d", &opt );
        if ( opt == 1 ) {
            int x; scanf ( "%d", &x );
            int ans = query ( x + 1 );
            printf ( "%d
", ans );
        } else {
            int x, y; scanf ( "%d%d", &x, &y );
            modify ( x + 1, y );
        }
    }
    return 0;
}