P3203 [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。

输出格式:

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

输入输出样例

输入样例#1:

1
2
3
4
5
6
4
1 2 1 1
3
1 1
2 1 1
1 1

输出样例#1:

1
2
2
3

说明

对于20%的数据 $n,m\le 10000$,
对于100%的数据 $n\le 200000$,$m\le 100000$

题解

分块,
每个块内每个点维护从该点出发跳多少次能跳出这个块,跳出这个块后到哪个位置,
从后往前扫预处理就是 $O(n)$的,
然后修改的时候只要修改一个块 ,$O(\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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
int qmax(int &x,int y) {if (x<y) x=y;}
int qmin(int &x,int y) {if (x>y) x=y;}
inline int read()
{
char s;int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(isdigit(s)));
if(s==EOF)exit(0);if(s=='-')base=-1,s=getchar();
while(isdigit(s)){k=k*10+(s^'0');s=getchar();}
return k*base;
}
inline void write(int x)
{
static char cnt,num[15];cnt=0;
if (!x) {putchar('0'); return;}
for (;x;x/=10) num[++cnt]=x%10;
for (;cnt;putchar(num[cnt--]+48));
putchar('\n');
}
const int maxn=200100;
int n,m,cnt,bj,x,y,size;
int a[maxn],k[maxn],c[maxn],p[maxn],r[maxn];
int main()
{
n=read();
size=sqrt(n);
for (int i=1;i<=n;i++)
{
a[i]=read();
k[i]=(i-1)/size+1;
qmax(r[k[i]],i);
}
cnt=k[n];
for (int i=n;i>=1;i--)//预处理
{
p[i]=i;
p[i]+=a[i];
c[i]++;
if (p[i]<=r[k[i]])
{
c[i]+=c[p[i]];
p[i]=p[p[i]];
}
}
m=read();
while (m--)
{
bj=read();
if (bj==1)//求解
{
int i=read()+1,s=0;
while (i<=n)
{
s+=c[i];
i=p[i];
}
write(s);
} else
{//修改
x=read()+1;y=read();
a[x]=y;
for (int i=x;i>r[k[x]-1];i--)
{
p[i]=i;
p[i]+=a[i];
c[i]=1;
if (p[i]<=r[k[i]])
{
c[i]+=c[p[i]];
p[i]=p[p[i]];
}
}
}
}
return 0;
}