分块 90pts 求助
查看原帖
分块 90pts 求助
383791
Others楼主2022/1/2 15:45

蒟蒻刚学 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;
}
2022/1/2 15:45
加载中...