题意L 在地上沿着一条直线摆上nnn个装置每个装置设定初始弹力系数kik_iki当绵羊达到第iii个装置时它会往后弹kik_iki步达到第ikiik_iiki个装置若不存在第ikiik_iiki个装置则绵羊被弹飞。绵羊想知道当它从第iii个装置起步时被弹几次后会被弹飞。为了使得游戏更有趣L 可以修改某个弹力装置的弹力系数任何时候弹力系数均为正整数。输入第一行包含一个整数nnn表示地上有nnn个装置装置的编号从0∼n−10 \sim n-10∼n−1。接下来一行有nnn个正整数依次为那nnn个装置的初始弹力系数。第三行有一个正整数mmm表示操作次数。接下来mmm行每行至少有两个数i,ji,ji,j。若i1i1i1你要输出从编号为jjj的装置出发被弹几次后被弹飞若i2i2i2则还会再输入一个正整数kkk表示编号为jjj的弹力装置的系数被修改成kkk。1≤n≤2×1051\le n \le 2\times 10^51≤n≤2×1051≤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 lbl[x],rbr[x];for(intil;ir;i)to[i]cnt[i]0;for(intir;il;i--){if(ia[i]r)to[i]ia[i],cnt[i]1;elseto[i]to[ia[i]],cnt[i]cnt[ia[i]]1;}}//原则上修改一个点会影响前面所有点的答案但是如此维护只影响块内该点的前驱//修改是容易的块内维护前驱即可...llquery(ll x){ll ret0;while(xn){retcnt[x];xto[x];//跳跃保持根号复杂度to与块有关}returnret;}//每个块的to,cnt相对独立代码复健一天写的代码奇短无比不知道以前在干什么……#includebits/stdc.husingnamespacestd;#definelllonglongconstll N2e59;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 lbl[x],rbr[x];for(intil;ir;i)to[i]cnt[i]0;for(intir;il;i--){if(ia[i]r)to[i]ia[i],cnt[i]1;elseto[i]to[ia[i]],cnt[i]cnt[ia[i]]1;}}voidinit(){bSizesqrt(n);cnt_bn/bSize;if(n%bSize)cnt_b;for(inti1;in;i)bel[i](i-1)/bSize1;for(inti1;icnt_b;i){bl[i](i-1)*bSize1;br[i]i*bSize;}br[cnt_b]n;for(intx1;xcnt_b;x)upd(x);}voidmodify(ll x,ll k)//指向块外的修改只影响块内{ll bxbel[x];a[x]k;upd(bx);}llquery(ll x){ll ret0;while(xn){retcnt[x];xto[x];//跳跃保持根号复杂度to与块有关}returnret;}intmain(){scanf(%lld,n);for(inti1;in;i)scanf(%lld,a[i]);init();scanf(%lld,Q);while(Q--){ll op,x,k;scanf(%lld%lld,op,x);x;if(op1)printf(%lld\n,query(x));else{scanf(%lld,k);modify(x,k);}}return0;}