蒟蒻刚学 OI,求大佬帮忙调调,第 9 个点 WA 了。
#include<bits/stdc++.h>
#define int long long
using namespace std;
template<typename zqw>void qr(zqw &x){
bool f=x=0;
char c=getchar();
while(!isdigit(c)) f|=c=='-',c=getchar();
while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
x=f?~(x-1):x;
return ;
}
int n,m,a[200005],s,bls,L[405],R[405],idx[200005],dp1[200005],dp2[200005],ans,opt,x,k;
signed main() {
qr(n);
s=sqrt(n),bls=(n+s-1)/s;
for(int i=1;i<=bls;i++){
L[i]=R[i-1]+1,R[i]=min(n,s*i);
for(int j=L[i];j<=R[i];j++) idx[j]=i;
}
for(int i=1;i<=n;i++){
qr(a[i]);
}
for(int i=1;i<=bls;i++){
for(int j=R[i];j>=L[i];j--){
if(j+a[j]>R[i]){
dp1[j]=1;
dp2[j]=j+a[j];
}else{
dp1[j]=dp1[j+a[j]]+1;
dp2[j]=dp2[j+a[j]];
}
}
}
qr(m);
while(m--){
qr(opt);
if(opt^2){
qr(x);
x++;
ans=0;
while(x<=n){
ans+=dp1[x];
x=dp2[x];
}
printf("%lld\n",ans);
}else{
qr(x),qr(k);
x++;
a[x]=k;
for(int i=x;i>=L[idx[x]];i--){
if(i+a[i]>R[idx[x]]){
dp1[i]=1;
dp2[i]=i+a[i];
}else{
dp1[i]=dp1[i+a[i]]+1;
dp2[i]=dp2[i+a[i]];
}
}
}
}
return 0;
}