我人傻常数大,但是复杂度是对的
查看原帖
我人傻常数大,但是复杂度是对的
91737
rex_qwq楼主2023/10/15 19:55

有人愿意告诉我的分块常数大在哪吗

#include<bits/stdc++.h>
//#pragma GCC optimize(3,"Ofast,no-stack-protector,unroll-loops,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,fma,popcnt,tune=native")
using namespace std;
#define endl '\n'
int n;
const int N=2e5+90;
int len=0;
int a[N];
int opt,pos,c,q;
int tag[N];
int L[N],R[N];
int E[N];
int step[N],to[N];
inline void modify(int pos,int val){
	register int x=E[pos];
	a[pos]=val;
	for(register int i=pos;i>=L[x];i--){
			to[i]=i+a[i];
			if(to[i]>R[x])step[i]=1;
			else to[i]=to[to[i]],step[i]=step[to[i]]+1;
		}
}
inline int ask(int pos){
	int ans=0;
	while(pos<=n)
		ans+=step[pos],pos=to[pos];
	return ans;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	len=sqrt(n);
	for(register int i=1;i<=n;i++)
		cin>>a[i];
	for(register int i=1;i<=len;i++)
		L[i]=(i-1)*len+1,R[i]=i*len;
	if(R[len]<n)
		++len,L[len]=R[len-1]+1,R[len]=n;
	for(register int i=1;i<=len;i++)
		for(register int j=R[i];j>=L[i];j--){
			to[j]=j+a[j];
			if(to[j]>R[i])step[j]=1;
			else step[j]=step[to[j]]+1,to[j]=to[to[j]];
			// cout<<j<<" "<<a[j]<<" "<<i<<" "<<to[j]<<" "<<step[j]<<endl;
		}
	cin>>q;
	for(register int i=1;i<=q;i++){
		cin>>opt>>pos;
		pos++;
		int x;
		if(opt&1)cout<<ask(pos)<<endl;
		else cin>>x,modify(pos,x);
		// cout<<step[3]<<" "<<114514<<endl;
	}
    return 0;
}
2023/10/15 19:55
加载中...