mxqz线段树合并
  • 板块学术版
  • 楼主Duramente
  • 当前回复4
  • 已保存回复4
  • 发布时间2022/3/27 21:39
  • 上次更新2023/10/28 05:21:52
查看原帖
mxqz线段树合并
257565
Duramente楼主2022/3/27 21:39

今天我在写 CF1009F 的时候,线段树合并被链卡 MLE 了。
这个题大意是这样,给一棵树,对每个点求子树内离他距离为 d 的数量的点最多时,d 最小是多少,我的想法是线段树维护每个点子树内不同深度的点的个数,然后向上线段树合并,然而在一条链的数据被卡 MLE 了。
提交记录。

submission

但我的理解是,我的动态开点线段树已经事先开好了内存,而且对于这样先合并儿子,再更新自己的 dep 的写法,遇上链感觉是最不容易被卡的,每次直接把儿子的线段树根复制过来,再 log 的时间插入一个新点(由于是链,所以每个深度都不同)本地测试开的节点数是 O(n) 级别的,所以为什么会 MLE 呢/yiw

2022/3/27 21:39
加载中...