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
1 2 1 1
3
1 1
2 1 1
1 1
Sample Output
2
3
3
HINT
Source
网上题解都是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[], cnt[], jum[], bl[]; void init ( int x ) {
int pos = x; cnt[x] = ;
while ( pos <= min ( bl[x] * blo, n ) ) {
cnt[x] ++;
pos += a[pos];
}
jum[x] = pos;
} int query ( int x ) {
int pos = x, ans = ;
while ( pos <= n ) ans += cnt[pos], pos = jum[pos];
return ans;
} void modify ( int x, int y ) {
int pos = x; cnt[x] = ; a[x] = y;
for ( int i = x; i >= blo * ( bl[x] - ) + ; i -- ) {
if ( i + a[i] <= min ( blo * bl[x], n ) )
cnt[i] = cnt[i+a[i]] + , jum[i] = jum[i+a[i]];
else cnt[i] = , jum[i] = i + a[i];
}
} int main ( ) {
scanf ( "%d", &n );
for ( int i = ; i <= n; i ++ ) scanf ( "%d", &a[i] );
blo = sqrt ( n );
for ( int i = ; i <= n; i ++ ) bl[i] = ( i + blo - ) / blo;
for ( int i = ; i <= n; i ++ ) init ( i );
scanf ( "%d", &m );
for ( int i = ; i <= m; i ++ ) {
int opt;
scanf ( "%d", &opt );
if ( opt == ) {
int x; scanf ( "%d", &x );
int ans = query ( x + );
printf ( "%d\n", ans );
} else {
int x, y; scanf ( "%d%d", &x, &y );
modify ( x + , y );
}
}
return ;
}