BZOJ 2002 Bounce 弹飞绵羊 [分块]

本身是一道lct裸题，为了证明分块的优越性，可用性，强行写了一波不擅长的分块。。。GG
分块思路很优秀，每个点记录跳出分块的步数以及跳到下一分块的哪个点

#include
#include
#include
#include
#include
#define inf 0x7fffffff
#define ll long long
using namespace std;
template<class T>
inline void read(T &res){T flag=1;static char ch;while((ch=getchar())>'9'||ch<'0')if(ch=='-')flag=-1;res=ch-'0';while((ch=getchar())>='0'&&ch<='9')res=res*10+ch-'0';res*=flag;
}
const int N = 200005;
int n,m,block,cnt;
int fa[N],sum[N],val[N],belong[N],l[N],r[N];
inline int judge(int x,int ret=0){while(1){ret+=sum[x];if(!fa[x])break;x=fa[x];}return ret;
}
int main(){read(n);block=sqrt(n*(double)log2((double)n*2.0));for(register int i=1;i<=n;i++)read(val[i]);if(n%block)cnt=n/block+1;else cnt=n/block;for(register int i=1;i<=cnt;i++)l[i]=(i-1)*block+1,r[i]=i*block;r[cnt]=n;for(register int i=1;i<=n;i++)belong[i]=(i-1)/block+1;for(register int i=n;i>0;i--){if(i+val[i]>n)sum[i]=1;else if(belong[i]==belong[i+val[i]])sum[i]=sum[i+val[i]]+1,fa[i]=fa[i+val[i]];else sum[i]=1,fa[i]=i+val[i];}read(m);for(register int x,y,f,i=1;i<=m;i++){read(f),read(x);x++;if(f==1)printf("%d\n",judge(x));else{read(y);val[x]=y;for(register int i=x;i>=l[belong[x]];i--)if(belong[i]==belong[i+val[i]])sum[i]=sum[i+val[i]]+1,fa[i]=fa[i+val[i]];else sum[i]=1,fa[i]=i+val[i];}}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！