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 le 10000)，对于(100\%)的数据(n le 200000),(m le 100000)
Output
对于每个i=1的情况，你都要输出一个需要的步数，占一行。
Sample Input
4
1 2 1 1
3
1 1
2 1 1
1 1
Sample Output
2
3
Analysis
这道题的正解是LCT?
不过这是省选题，一定有其他的解法，这里就有一个分块做法。
O(n)维护两个数组to和outto,to代表每个位置跳到块内最后一个位置的最少步数，outto表示这个位置跳到第二个块的新位置。这两个数组倒着维护。
然后就能做了。
询问和修改的时间复杂度都是(O(sqrt n))，因为一共(sqrt n)个块,每个块内(sqrt n)个元素。
code
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int read()
{
int ans = 0,op = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-') op = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
ans *= 10;
ans += ch - '0';
ch = getchar();
}
return ans * op;
}
const int maxn = 2e5 + 5;
int seq[maxn];
int blo[10005];
int to[maxn];
int outto[maxn];
int m,n;
int cnt,num,cntt=1;
int qpos(int x)
{
return x % cnt == 0 ? x / cnt : x / cnt + 1;
}
int qlast(int x)
{
if(qpos(x) == num)
return n;
return cnt * qpos(x);
}
int qfirst(int x)
{
return cnt * (qpos(x) - 1) + 1;
}
int main()
{
n = read();
cnt = sqrt(n);
num = qpos(n);
for(int i=1;i<=n;i++)
seq[i] = read();
for(int i=n;i>=1;i--)
{
if(i + seq[i] > qlast(i))
{
to[i] = i + seq[i];
outto[i] = 1;
}
else
{
to[i] = to[i+seq[i]];
outto[i] = outto[i+seq[i]] + 1;
}
}
// printf("
***
");
// for(int i=1;i<=n;i++)
// printf("%d ",to[i]);
// printf("
");
// for(int i=1;i<=n;i++)
// printf("%d ",outto[i]);
// printf("
***
");
m = read();
for(int ct=1;ct<=m;ct++)
{
int ju;
ju = read();
if(ju == 1)
{
int x,ans;
x = read();
x+=1;
ans = outto[x];
x = to[x];
while(x <= n)
{
ans += outto[x];
x = to[x];
}
printf("%d
",ans);
}
else
{
int x,k;
x = read();
k = read();
x+=1;
seq[x] = k;
for(int i=x;i>=qfirst(x);i--)
{
if(i + seq[i] > qlast(i))
{
to[i] = i + seq[i];
outto[i] = 1;
}
else
{
to[i] = to[i+seq[i]];
outto[i] = outto[i+seq[i]] + 1;
}
}
}
}
return 0;
}