对于本题数据的一些说明

P3806 【模板】点分治 1

一扶苏一 @ 2020-02-08 00:56:40

  • 谷的评测机是不存在爆栈一说的,RE 一般只可能是产生了段错误或返回值异常等。
  • 树的所有边权权值总和达到了 10^8,但是询问只到了 10^7,因此在统计子树内路径权值时,需要在经过权值大于 10^7 的时候及时返回,否则由于用了桶来统计路径,大于 10^7 的权值会爆数组,第一篇题解在 #7 会 RE 就是这个原因。如果您也 RE 了,不妨检查一下这里。
  • 如果您是每次询问都点分一次然后被卡常了,可以考虑建出点分树后统一处理所有的询问(也可以像第一篇题解一样一边点分一边处理询问),因为本题点分做法的时间复杂度是 O(nm \log n),但是点分的复杂度是 O(n \log n),如果只点分一次,它的巨大常数是不会乘到总复杂度里面去的,这样对效率有非常大的提高。

by int32 @ 2021-08-07 15:30:18


by _8762 @ 2021-10-04 20:30:01

%%%%%


by blank_name @ 2021-10-19 22:28:51

用bitset桶可以硬开1e8


by Lazy_Labs @ 2022-05-08 09:00:49


by St_john @ 2022-06-08 22:52:27

能不能扩大一下时间限制(500ms吧)


by chs007 @ 2022-07-04 09:42:09

RE第一种情况好像把所有数组开到10^6以上也能过???(反正我过了


by bmqt @ 2022-07-21 11:15:01

%%%%%%%%%%%%%%


by MeowScore @ 2022-07-30 16:23:58

T 炸了,改成一次点分真的起飞了/se


by Raurusawa @ 2022-10-05 20:46:21

有时候递归参数写引用也会RE 改成返回值就AC


by scp020 @ 2022-12-19 12:56:17

草,我中招了……


上一页 | 下一页