关于树上莫队不同写法的常数
  • 板块学术版
  • 楼主Mobius127
  • 当前回复7
  • 已保存回复7
  • 发布时间2023/8/12 12:02
  • 上次更新2023/11/3 04:18:42
查看原帖
关于树上莫队不同写法的常数
341102
Mobius127楼主2023/8/12 12:02

事情酱紫的:我在补之前联测的某题,做法大概是在 T1,T2T1,T2 上各自维护一条到根的路径(终点不一定编号相同),计算这两条路径在 T3T3 上对应点两两路径和。(T1,T2,T3T1, T2, T3 结点个数相同)

正解是直接在 T1,T2T1, T2 上通过树分块来维护路径,我的做法是把 T1,T2T1, T2 拍成括号序,然后跑一个类似于序列莫队的东西。后面的部分都是在 T3T3 上点分树算算。复杂度都是 O(nmlog⁡n)O(n\sqrt{m}\log n) 的。

但是事实是 std 最慢也就 2s 出头,我的 code 稳定在 8s 到 10s。

想知道为什么常数区别那么大(明明括号序版也就自带一个 2 的常数?)。

2023/8/12 12:02
加载中...