（分块）洛谷 P3203 弹飞绵羊 题解

题意

L 在地上沿着一条直线摆上nnn个装置，每个装置设定初始弹力系数kik_iki​，当绵羊达到第iii个装置时，它会往后弹kik_iki​步，达到第i+kii+k_ii+ki​个装置，若不存在第i+kii+k_ii+ki​个装置，则绵羊被弹飞。

绵羊想知道当它从第iii个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，L 可以修改某个弹力装置的弹力系数，任何时候弹力系数均为正整数。

输入：

第一行包含一个整数nnn，表示地上有nnn个装置，装置的编号从0∼n−10 \sim n-10∼n−1。

接下来一行有nnn个正整数，依次为那nnn个装置的初始弹力系数。

第三行有一个正整数mmm，表示操作次数。接下来mmm行每行至少有两个数i,ji,ji,j。

• 若i=1i=1i=1，你要输出从编号为jjj的装置出发被弹几次后被弹飞

• 若i=2i=2i=2，则还会再输入一个正整数kkk，表示编号为jjj的弹力装置的系数被修改成kkk。

1≤n≤2×1051\le n \le 2\times 10^51≤n≤2×105，1≤m≤1051\le m \le 10^51≤m≤105。

思路

upd：一年后回来复健 OI 了，复习到分块看到这道题。

太久没有看过题目，我是根据查询时候，发现维护全局的跳跃终点和跳跃次数是O(1)O(1)O(1)的，但是修改牵一发而动全身需要O(n)O(n)O(n)。遇到这种就要想到用分块均衡：

考虑牺牲查询时候的复杂度，变为O(n)O(\sqrt{n})O(n​)，转为维护块内每个点跳出块的落点toito_itoi​和次数cnticnt_icnti​。这样修改块内某个值的时候，因为其他块的参数指向后继块，这些参数只与块内的kkk有关，所以修改当前块对其他块没有影响。

voidupd(ll x){ll l=bl[x],r=br[x];for(inti=l;i<=r;i++)to[i]=cnt[i]=0;for(inti=r;i>=l;i--){if(i+a[i]>r)to[i]=i+a[i],cnt[i]=1;elseto[i]=to[i+a[i]],cnt[i]=cnt[i+a[i]]+1;}}//原则上修改一个点会影响前面所有点的答案，但是如此维护只影响块内该点的前驱//修改是容易的，块内维护前驱即可...llquery(ll x){ll ret=0;while(x<=n){ret+=cnt[x];x=to[x];//跳跃保持根号复杂度，to与块有关？}returnret;}//每个块的to,cnt相对独立

代码

复健一天写的代码奇短无比，不知道以前在干什么……

#include<bits/stdc++.h>usingnamespacestd;#definelllonglongconstll N=2e5+9;ll n,Q;ll a[N];ll bSize,cnt_b,bel[N],bl[N],br[N];ll to[N],cnt[N];voidupd(ll x){ll l=bl[x],r=br[x];for(inti=l;i<=r;i++)to[i]=cnt[i]=0;for(inti=r;i>=l;i--){if(i+a[i]>r)to[i]=i+a[i],cnt[i]=1;elseto[i]=to[i+a[i]],cnt[i]=cnt[i+a[i]]+1;}}voidinit(){bSize=sqrt(n);cnt_b=n/bSize;if(n%bSize)cnt_b++;for(inti=1;i<=n;i++)bel[i]=(i-1)/bSize+1;for(inti=1;i<=cnt_b;i++){bl[i]=(i-1)*bSize+1;br[i]=i*bSize;}br[cnt_b]=n;for(intx=1;x<=cnt_b;x++)upd(x);}voidmodify(ll x,ll k)//指向块外的，修改只影响块内{ll bx=bel[x];a[x]=k;upd(bx);}llquery(ll x){ll ret=0;while(x<=n){ret+=cnt[x];x=to[x];//跳跃保持根号复杂度，to与块有关？}returnret;}intmain(){scanf("%lld",&n);for(inti=1;i<=n;i++)scanf("%lld",&a[i]);init();scanf("%lld",&Q);while(Q--){ll op,x,k;scanf("%lld%lld",&op,&x);x++;if(op==1)printf("%lld\n",query(x));else{scanf("%lld",&k);modify(x,k);}}return0;}