弹飞绵羊
题目的网址为:
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
begin
if o+k[o]>r
then
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