关于点分治复杂度
  • 板块学术版
  • 楼主Resolute_Faith
  • 当前回复8
  • 已保存回复8
  • 发布时间2022/9/4 12:14
  • 上次更新2023/10/27 12:36:35
查看原帖
关于点分治复杂度
754746
Resolute_Faith楼主2022/9/4 12:14

想不通,如果单次淀粉质复杂度为 O(nlogn)\mathcal{O}({n\log n}) 的话,那么进行 mm 次询问,时间复杂度应当是 O(nmlogn)\mathcal{O}(nm\log n),事实上淀粉质模板里大多数题解都是这样分析的。

那既然如此,为什么昨晚 ABC F 题采用淀粉质做法,时间复杂度会是 O(nlogn)\mathcal{O}(n\log n) 呢,其中询问跟点数都达到了 2×1052\times 10^5,比常见的淀粉质题目都大了特别多。

https://www.luogu.com.cn/paste/n7rh0ls4

2022/9/4 12:14
加载中...