一直听主力讲分块大法好，xllend3似乎证明莫队都可以用分块做！（%一发）

BZOJ传送门

一开始看到标签写着Splay 启发式合并感觉很厉害的样子，然后发现分块可以操！

思路：把N个蹦床分成sqrt(n）块，然后在每块里记录这个点飞出这个块要的步数和会飞到哪个点。
修改：把这个块里的点都重新算一遍，O（n^0.5)
询问：显然O（n^0.5）

#include <cstdio>
#include <cmath>
using namespace std;
#define maxn 200010
#define INF 0x7f7f7f7f
int a[maxn],p[maxn],num[maxn],size;
int LG(int x)//询问X属于哪个块
{
	return (x-1)/size+1;
}
int head(int x)//询问第x块的头
{
	return (x-1)*size+1;
}

int main()
{
	int n;
	scanf("%d",&n);
	for (int i = 1;i <= n;i++)
		scanf("%d",&a[i]);
	size = sqrt(n);
	if (size*size < n) size++;
	for (int i = n;i >= 1;i--)
	{
		if (i+a[i] > n)
			p[i] = INF,num[i] = 1;
		else if (LG(i+a[i])!=LG(i))
			p[i] = i+a[i],num[i] = 1;
		else p[i] = p[i+a[i]],num[i] = 1+num[i+a[i]];
	}
	int q;
	scanf("%d",&q);
	for (;q--;)
	{
		int x;
		scanf("%d",&x);
		if (x == 1)
		{
			int y,ans = 0;
			scanf("%d",&y);
			for (y++;y < INF;y = p[y])ans += num[y];
			printf("%d\n",ans);
		}
		else
		{
			int y,z;
			scanf("%d%d",&y,&z);
			a[++y] = z;
			int t = head(LG(y));
			for (;y >= t;y--)
			{
				if (y+a[y] > n)
					p[y] = INF,num[y] = 1;
				else if (LG(y+a[y])!=LG(y))
					p[y] = y+a[y],num[y] = 1;
				else p[y] = p[y+a[y]],num[y] = 1+num[y+a[y]];
			}
		}
	}
	return 0;
}

此外RMQ问题也可以用分块解决。codevs传送门

代码如下

#include <cstdio>
#include <cmath>
#define maxn 100010
using namespace std;
int a[maxn],sum[400],size;
int LG(int x)
{
	return (x-1)/size+1;
}
int tail(int x)
{
	return x*size;
}
int head(int x)
{
	return (x-1)*size+1;
}
int main()
{
	int n;
	scanf("%d",&n);
	for (int i = 1;i <= n;i++)
		scanf("%d",&a[i]);
	int q;
	scanf("%d",&q);
	size = sqrt(n);
	if (size*size < n) size++;
	for (int i = 1;i <= size-1;i++)
		for (int j = 1;j <= size;j++)
			sum[i] += a[(i-1)*size+j];
	for (int i = (size-1)*size+1;i <= n;i++)
		sum[size] += a[i];
	for (;q--;)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		if (x == 1)
		{
			sum[LG(y)] += z;
			a[y] += z;
		}
		else
		{
			int ans = 0;
			if (LG(y)==LG(z))
			{
				for (int i = y;i <= z;i++)
					ans += a[i];
			}
			else
			{
				int t = tail(LG(y));
				for (int i = y;i <= t;i++)
					ans += a[i];
				t = head(LG(z));
				for (int i = t;i <= z;i++)
					ans += a[i];
				y = LG(y)+1;
				z = LG(z)-1;
				for (int i = y;i <= z;i++)
					ans += sum[i];
			}
			printf("%d\n",ans);
		}
	}
	return 0;
}