洛谷P3203弹飞绵羊

传送门啦

非常神奇的分块大法。

每块分 √N 个元素 ， 预处理出来：对于每个点，记录两个量：一个是它要弹几次才能出它所在的这个块，另外一个是它弹出这个块后到哪个点。

查询操作：一块一块跳过去 单次复杂度 O(√N)

修改操作：只需要把相应的块改一遍就好了 这个也是O(√N)

#include <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

#include <cmath>

using namespace std;

const int maxn = 200005;

const int maxm = 100005;

inline int read(){

	char ch = getchar();

	int f = 1 , x = 0;

	while(ch > '9' || ch < '0'){if(ch == '-')f = -1;ch =getchar();}

	while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + ch - '0';ch = getchar();}

	return x * f;

}

int n,a[maxn],m,flag,x,y,ans;

int l[maxn],r[maxn],cnt,belong[maxn],to[maxn],step[maxn];

void init(){

	int t = sqrt(n);

	if(n / t)  cnt = n / t + 1;

	else cnt = n / t;

	for(int i=1;i<=cnt;i++){

		l[i] = r[i-1] + 1;

		r[i] = min(l[i] + t - 1 , n);

	}

	int x = 1;

	for(int j=1;j<=n;j++){

		belong[j] = x;

		if(j == r[x] && x <= cnt)  x++;

	}

	for(int i=n;i>=1;i--){

		to[i] = i + a[i];

		if(to[i] > r[belong[i]])  step[i] = 1;

		else {

			step[i] = step[to[i]] + 1;

			to[i] = to[to[i]];

		}

	}

}

int main(){

	n = read();

	for(int i=1;i<=n;i++)  a[i] = read();

	init();

	m = read();

	while(m--){

		ans = 0;

		flag = read();

		if(flag == 1){

			x = read(); x++;

			while(x <= n){

				ans += step[x];

				x = to[x];

			}

			printf("%d\n",ans);

		}

		else {

			x = read(); y = read();

			x++;

			a[x] = y;

			for(int i=r[belong[x]];i>=l[belong[x]];i--){

				to[i] = i + a[i];

				if(to[i] > r[belong[i]]) step[i] = 1;

				else {

					step[i] = step[to[i]] + 1;

					to[i] = to[to[i]];

				}

			}

		}

	}

	return 0;

}