没人吗，，，，蒟蒻求Dalao啊
by 冈崎梦美 @ 2018-05-06 13:26:04
在更新操作中要修改整个块。
by AThousandSuns @ 2018-05-06 13:30:23
链接发犇犇里给大佬看看吧>->@[LGW2016B02](/space/show?uid=41953)
by YLZZZ @ 2018-05-06 13:30:32
@[AThousandSuns](/space/show?uid=72118) 为什么啊……
by 冈崎梦美 @ 2018-05-06 13:39:23
@[LGW2016B02](/space/show?uid=41953) 你想想2和5和7在同一个块内，从2跳到5，从5跳到7，那如果更新成5就能一步跳到下一块的9，2是不也要更新？
by AThousandSuns @ 2018-05-06 13:41:55
@[AThousandSuns](/space/show?uid=72118) 那怎么改啊巨佬……表示不会写区间更新……$\color{black} \text{} \colorbox{black}{潜台词：帮我写下好吗……}$祝您RP大涨啊……
by 冈崎梦美 @ 2018-05-06 14:01:35
@[LGW2016B02](/space/show?uid=41953) 给你个提示：
从后往前遍历整个块，如果跳得出这个块，to[i]=i+k[i]，times[i]=1。否则to[i]=to[i+k[i]],times[i]=times[i+k[i]]+1。
by AThousandSuns @ 2018-05-06 14:06:53
@[AThousandSuns](/space/show?uid=72118) 改成区间更新也没用啊……WA的点和以前都一模一样
```
#include<bits/stdc++.h>
#define maxn 200001
using namespace std;
int n,m;
int a[maxn],times[maxn],to[maxn],l[maxn],r[maxn],belong[maxn],block;
void write(int x)
{
if (x>9) write(x/10);
putchar(x%10+'0');
}
int query(int x)
{
int now=x,steps=0;
while(now<=n)
{
steps+=times[now];
now=to[now];
}
return steps;
}
void build()
{
block=sqrt(n);
int num=n/block;if (n%block) num++;
for(int i=1;i<=num;i++)
{
l[i]=(i-1)*block+1;r[i]=i*block;
}
r[num]=n;
for(int i=1;i<=num;i++)
{
for(int j=l[i];j<=r[i];j++)
belong[j]=i;
}
}
void doit()
{
for(int i=1;i<=n;i++)
{
int now=i,cnt=0;
while(true)
{
cnt++;
now+=a[i];
if (now>r[belong[i]]) break;
}
to[i]=now;times[i]=cnt;
}
}
void change(int x,int y)
{
a[x]=y;
for(int i=r[belong[x]];i>=l[belong[x]];i--)
{
if (i+a[i]>r[belong[i]])
{
to[i]=i+a[i];
times[i]=1;
}
else
{
to[i]=to[i+a[i]];
times[i]=times[i+a[i]]+1;
}
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
build();
doit();
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d %d",&x,&y);
if (x==1)
{
write(query(y+1));
putchar('\n');
}
if (x==2)
{
int t;
scanf("%d",&t);
change(y+1,t);
}
}
return 0;
}
```
by 冈崎梦美 @ 2018-05-06 14:21:48
@[LGW2016B02](/space/show?uid=41953) emmm......doit里面应该是now+=a[now]，不是now+=a[i]
by AThousandSuns @ 2018-05-06 14:43:40
@[AThousandSuns](/space/show?uid=72118) 人生第一道紫题通过！感谢Julao！
by 冈崎梦美 @ 2018-05-06 14:50:44