链接:https://www.lydsy.com/JudgeOnline/problem.php?id=2002
思路:和之前那道树分块的题很像,只不过那道是在树上,这道简单些在序列上
还是维护两个数组:
num[] 跳出当前块需要的次数
nex[] 跳出当前块到达的点的下标
实现代码:
#include<bits/stdc++.h>
using namespace std;
const int M = 2e5+;
int n,m,block,cnt,l[M],r[M],a[M],blo[M],nex[M],num[M],op;
int query(int x){
int sum = ;
while(x){
sum += num[x];
x = nex[x];
}
return sum;
} int main()
{
int x,y;
scanf("%d",&n);
block = sqrt(n);
for(int i = ;i <= n;i ++){
scanf("%d",&a[i]);
}
for(int i = ;i <= n;i ++) blo[i] = (i-)/block+;
for(int i = ;i <= blo[n];i++) l[i] = (i-)*block+;
for(int i = n;i > ;i --){
if(i + a[i] > n) num[i] = ;
else if(blo[i] == blo[i+a[i]])
num[i] = num[i+a[i]]+,nex[i] = nex[i+a[i]];
else
num[i] = ,nex[i] = i+a[i];
}
scanf("%d",&m);
for(int i = ;i <= m;i ++){
scanf("%d%d",&op,&x);
x++;
if(op == ) printf("%d\n",query(x));
else{
scanf("%d",&y);
a[x] = y;
for(int i = x;i >= l[blo[x]];i --){
if(blo[i] == blo[i+a[i]])
num[i] = num[i+a[i]]+,nex[i] = nex[i+a[i]];
else num[i] = ,nex[i] = i+a[i];
}
}
}
return ;
}