保存帖子
发现
索引
热门
陶片放逐
关于
对于本题数据的一些说明
板块
P3806 【模板】点分治 1
楼主
一扶苏一
扶咕咕
当前回复
56
已保存回复
56
发布时间
2020/2/8 00:56
上次更新
2024/11/11 08:17:05
查看原帖
更新帖子
被骇客
银
狼
阻止的越权访问
保存失败
对于本题数据的一些说明
一扶苏一
扶咕咕
楼主
2020/2/8 00:56
谷的评测机是不存在爆栈一说的，RE
一般
只可能是产生了段错误或返回值异常等。
树的所有边权权值总和达到了
1
0
8
10^8
1
0
8
，但是询问只到了
1
0
7
10^7
1
0
7
，因此在统计子树内路径权值时，需要在经过权值大于
1
0
7
10^7
1
0
7
的时候及时返回，否则由于用了桶来统计路径，大于
1
0
7
10^7
1
0
7
的权值会爆数组，第一篇题解在 #7 会 RE 就是这个原因。如果您也 RE 了，不妨检查一下这里。
如果您是每次询问都点分一次然后被卡常了，可以考虑建出点分树后统一处理所有的询问（也可以像第一篇题解一样一边点分一边处理询问），因为本题点分做法的时间复杂度是
O
(
n
m
log
n
)
O(nm \log n)
O
(
nm
lo
g
n
)
，但是点分的复杂度是
O
(
n
log
n
)
O(n \log n)
O
(
n
lo
g
n
)
，如果只点分一次，它的巨大常数是不会乘到总复杂度里面去的，这样对效率有非常大的提高。
2020/2/8 00:56
加载中...
