HNOI 2010 弹飞绵羊 （分块/LCT）

发表于 |
字数统计: 873字 | 阅读时长 ≈ 4min

【HNOI2010】弹飞绵羊

问题描述

某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿着一条直线摆上n个装置，每个装置设定初始弹力系数ki，当绵羊达到第i个装置时，它会往后弹ki步，达到第i+ki个装置，若不存在第i+ki个装置，则绵羊被弹飞。绵羊想知道当它从第i个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，Lostmonkey可以修改某个弹力装置的弹力系数，任何时候弹力系数均为正整数。

输入格式

第一行包含一个整数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

输出格式

对于每个i=1的情况，你都要输出一个需要的步数，占一行。

样例输入

4
1 2 1 1
3
1 1
2 1 1
1 1

样例输出

2
3

如果学了LCT，那么此题就是模板题，因此主要说说分块的做法

一开始的想法肯定是每次直接暴力跳，然而这样的复杂度是$n^2$的，那么，有什么办法可以减少跳的次数呢，考虑分块，如果将整个区间分成$\sqrt{n}$块，并且每次跳一块，那么最多只跳$\sqrt{n}$次，理论可过。
具体来讲，对于每一块中的每一个装置，记下他会跳到下一块中的那一个位置，并且记下跳跃次数，然后每次就可以跳一块了。

考虑修改，一个位置被修改，由于每次都只跳了一块，那么影响肯定只影响到一块，因此重新算修改位置所在块的值就好了。

总时间复杂度$n\sqrt{n}$

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define N 400005
using namespace std;
int n,m,S,T,A[N],NE[N],C[N],ID[N];
void MD(int x)
{
	int i,l=(ID[x]-1)*S;
	for(i=x;i>l;i--)
	{
		if(ID[i+A[i]]!=ID[i])NE[i]=i+A[i],C[i]=1;
		else NE[i]=NE[i+A[i]],C[i]=C[i+A[i]]+1;
	}
}
int GA(int x)
{
	int sum=0;
	while(x<=n)
	{
		sum+=C[x];
		x=NE[x];
	}
	return sum;
}
int main()
{
	int i,j,k,p;
	scanf("%d",&n);S=sqrt(n);
	for(i=1;i<=n;i++)ID[i]=(i-1)/S+1;
	for(i=1;i<=n;i++)scanf("%d",&A[i]);
	scanf("%d",&m);T=ID[n];
	for(i=1;i<=T;i++)
	for(j=min(n,i*S);j>(i-1)*S;j--)
	{
		if(ID[j+A[j]]!=ID[j])NE[j]=j+A[j],C[j]=1;
		else NE[j]=NE[j+A[j]],C[j]=C[j+A[j]]+1;
	}
	for(i=1;i<=m;i++)
	{
		scanf("%d",&j);
		if(j==1)
		{
			scanf("%d",&k);k++;
			printf("%d\n",GA(k));
		}
		else
		{
			scanf("%d%d",&k,&p);
			k++;A[k]=p;MD(k);
		}
	}
}