请求加入题解区

Butterfly__qwq @ 2024-02-29 14:36:57

by Butterfly__qwq @ 2024-02-29 14:37:12

@feecle6418 @小粉兔

by Butterfly__qwq @ 2024-02-29 14:57:51

@User_Unauthorized 我知道什么是Sqrt Tree，但是Sqrt Tree是每层的块长都是上一层的根号，显然和这个东西不一样

by Deuteron @ 2024-02-29 15:01:02

@FantasyB 这个和sqrt tree不是本质一样吗

by Butterfly__qwq @ 2024-02-29 15:02:56

@小可爱萌萌哒 为什么本质一样/kk

Sqrt Tree能做这道题吗/oh

by Butterfly__qwq @ 2024-02-29 15:03:43

用Sqrt Tree的话pushdown巨大的开销难道不会使复杂度骤增吗

by Butterfly__qwq @ 2024-02-29 15:04:59

@小可爱萌萌哒 这个东西多分几层不就是和完全不分一样了吗

by 大眼仔Happy @ 2024-02-29 15:05:13

不解，那你咋不搞个 \log n 层呢

by Butterfly__qwq @ 2024-02-29 15:05:58

@大眼仔Happy 因为这样复杂度会多个log

我这样不是只会常数多个2吗

by Butterfly__qwq @ 2024-02-29 15:06:31

@大眼仔Happy 而且这个东西实测是比\log n层的线段树要快的

by 大眼仔Happy @ 2024-02-29 15:14:13

@FantasyB 不知道，看起来我的普通线段树就比你快

你用个 scanf/printf 看看多少时间