BZOJ 2002 Bounce 弹飞绵羊 [Hnoi2010]

    xiaoxiao2025-01-19  12

    弹飞绵羊

    题目的网址为:

    http://www.lydsy.com/JudgeOnline/problem.php?id=2002

    题目大意

    有N个点,每个点有一个系数a[i],你处于位置i可以走到i+a[i],若i+a[i]>n则你走出了地图。 现M个操作有两种: 1、把a[j]修改为k。 2、询问你位于点j时,需要走多少部走出地图。

    数据范围

    1<=n<=200000, 1<=m<=100000。

    题解

    这是一道经典的LCT(动态树)例题,然而,我这个蒟蒻,并不会用动态树,我只会分块这种相对低级的方法。

    将原序列分成 n 块, ei 表示当前 i 跳出i所在的那一块需要的步数, eni 表示跳出块后的位置。

    执行询问操作时,只需要不断地跳出下一个块,跳到不能再跳为止,最多跳 n 次。具体实现如下:

    ans:=0; while op<=n do begin ans:=ans+e[op]; op:=en[op]; end;

    执行修改操作时,只需修改本块中在该数之前的 ei eni ,从前往后修改,最多修改 n 次。具体实现如下:

    for o:=op downto l do //l为op所在块中的左边界 begin if o+k[o]>r then //r为op所在块中的右边界 begin en[o]:=u; e[o]:=1; end else begin en[o]:=en[u]; e[o]:=e[u]+1; end; end;

    初始化的方法跟在执行修改操作时的更新方法差不多,就不多讲了。 总时间复杂度 O (m n ),分块算法,奥妙重重!

    Code(Pascal)

    var k,en,ne:array[0..300000] of longint; ku,l,r,i,j,m,n,o,p,u,op,ans:longint; function min(a,b:Longint):longint; begin if a<b then exit(a) else exit(b); end; begin readln(n); for i:=1 to n do read(k[i]); ku:=trunc(sqrt(n)); p:=n div ku; if n mod p<>0 then inc(ku); for i:=1 to ku do begin l:=(i-1)*p+1; r:=min(i*p,n); for o:=r downto l do begin u:=o+k[o]; if u>r then begin en[o]:=u; ne[o]:=1; end else begin en[o]:=en[u]; ne[o]:=ne[u]+1; end; end; end; readln(m); for i:=1 to m do begin read(op); if op=1 then begin readln(op); inc(op); ans:=0; while op<=n do begin ans:=ans+ne[op]; op:=en[op]; end; writeln(ans); end else begin readln(op,u); inc(op); k[op]:=u; l:=(op div p)*p+1; r:=l+p-1; if op mod p=0 then begin l:=l-p; r:=r-p; end; for o:=op downto l do begin u:=o+k[o]; if u>r then begin en[o]:=u; ne[o]:=1; end else begin en[o]:=en[u]; ne[o]:=ne[u]+1; end; end; end; end; end.
    转载请注明原文地址: https://ju.6miu.com/read-1295640.html
    最新回复(0)