@[arfa](/space/show?uid=77760)
分块不是正解喂
by x_angelkawaii_x @ 2018-10-03 11:28:04
@[arfa](/space/show?uid=77760)
理论上时间复杂度在可接受范围内的都是正解(逃
而且这题用分块很好写的说
我就是这么过的我会乱说?(逃
AC Code:
```
var
bounce,get,pace:array [-1..210000] of longint; // 分别是弹力,到下一块,的步数
node_num,block_num,mode,ans,l,k,i,j,n,m:longint;
function Locate(node:longint):longint;
begin
exit((node - 1) div node_num + 1);
end;
procedure Ready;
begin
read(n);
node_num := trunc(sqrt(n));
block_num := Locate(n);
for i := 1 to n do
read(bounce[i]);
read(m);
for i := n downto 1 do begin
l := Locate(i) * node_num;
if (i + bounce[i] > n) then begin
get[i] := 0;
pace[i] := 1;
continue;
end;
if (i + bounce[i] > l) then begin
get[i] := i + bounce[i];
pace[i] := 1;
end
else begin
get[i] := get[i + bounce[i]];
pace[i] := pace[i + bounce[i]] + 1;
end;
end;
end;
begin
Ready;
for i:=1 to m do begin
read(mode);
if mode = 1 then begin
ans := 0;
read(l);
inc(l);
j := l;
while j > 0 do begin
inc(ans,pace[j]);
j:=get[j];
end;
writeln(ans);
end
else begin
read(l,k);
inc(l);
bounce[l] := k;
for j := Locate(l) * node_num downto (Locate(l) - 1) * node_num + 1 do begin
if (j + bounce[j] > n) then begin
get[j] := 0;
pace[j] := 1;
continue;
end;
if (j + bounce[j] > Locate(l) * node_num) then begin
get[j] := j + bounce[j];
pace[j] := 1;
end
else begin
get[j] := get[j + bounce[j]];
pace[j] := pace[j + bounce[j]] + 1;
end;
end;
end;
end;
end.
```
这位老哥没判跳出边界,导致越界
by Aleph1022 @ 2018-10-05 22:26:21
> %%% 小学 $AK\ ACM$ 巨佬 @[I_love_him52](/space/show?uid=75840)
by arfa @ 2018-10-05 22:32:17
@[沉迷学习的YSJ](/space/show?uid=93483) 可以用分块过,而且这题就是完完全全照搬的CF13E的题目(没想到出题人改都不改一点),而CF的题解就是用的分块。
by Euler_Pursuer @ 2018-10-24 17:16:54
@[孤独·粲泽](/space/show?uid=50871)
这么久的帖子你还回我
我就想问问你为什么不用更可爱的$LCT$呢
by x_angelkawaii_x @ 2018-10-24 17:23:40
@[沉迷学习的YSJ](/space/show?uid=93483) 因为太弱了以至于不会$LCT$,只能膜您%%%。
by Euler_Pursuer @ 2018-10-24 18:18:29