【bzoj2002】【Hnoi2010】【Bounce】【弹飞绵羊】【分块】

题目大意

有n个格，可以在i往后跳a[i]个格，修改a[i]，询问i跳多少次跳出这n个格。

解题思路

这是一道lct模板题，显然a[i]就是i的father，修改就是割一条边连一条边，询问一个点的深度。然而我并不会lct，只会打暴力。我们可以分块，维护跳到下一个块的花费，修改暴力重构当前块的所有点跳到下一个块的花费，询问一个块一个块的跳，当一个块大小为 n√ 时复杂度为 O(nn√)

code

#include<set> #include<cmath> #include<cstdio> #include<cstring> #include<algorithm> #define LL long long #define fo(i,j,k) for(int i=j;i<=k;i++) #define fd(i,j,k) for(int i=j;i>=k;i--) using namespace std; int const maxn=200000; int n,m,a[maxn+10],next[maxn+10],cnt[maxn+10]; int main(){ freopen("d.in","r",stdin); freopen("d.out","w",stdout); scanf("%d",&n); int size=sqrt(n); fo(i,0,n-1)scanf("%d",&a[i]); fo(i,0,n-1){ next[i]=i; for(;(next[i]<n)&&(i/size==next[i]/size);next[i]+=a[next[i]],cnt[i]++); } scanf("%d",&m); fo(i,1,m){ int x,y;scanf("%d%d",&x,&y); if(x==1){ int ans=0; for(;y<n;ans+=cnt[y],y=next[y]); printf("%d\n",ans); }else{ int z;scanf("%d",&z); a[y]=z;next[y]=y;cnt[y]=0; for(;(next[y]<n)&&(y/size==next[y]/size);next[y]+=a[next[y]],cnt[y]++); fd(j,y-1,0) if(y/size==j/size){ if(j/size==(j+a[j])/size){ next[j]=next[j+a[j]]; cnt[j]=cnt[j+a[j]]+1; } }else break; } } return 0; }