2002: [Hnoi2010]Bounce 弹飞绵羊
Time Limit: 10 Sec Memory Limit: 259 MBSubmit: 14802 Solved: 7507[][][]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
网上题解都是LCT？？QAQ明明就是分块暴力跳嘛！是随手a的第一道分块叻！要注意的就是修改操作从后往前更新就是$O(\sqrt{n})$，正着就$O(\sqrt{n}*\sqrt{n})$叻QAQ，还有最后一块可能并没有占满整个块，导致跳出$n$跳不出块就会死循环，所以一定要取$min$！！
#include#include #include 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\n", ans ); } else { int x, y; scanf ( "%d%d", &x, &y ); modify ( x + 1, y ); } } return 0;}