关于fhq-treap有交并
  • 板块学术版
  • 楼主Rain_chr
  • 当前回复7
  • 已保存回复7
  • 发布时间2024/4/11 08:50
  • 上次更新2024/4/11 15:42:20
查看原帖
关于fhq-treap有交并
684254
Rain_chr楼主2024/4/11 08:50

之前看过学长转载的博客,发现这样复杂度是 O(nlog⁡nlog⁡V)O(n\log n\log V)的,不过这篇博客并没有细说实现方式。

我自己编了一个实现方式,在几道题目上都能通过,不过还是不太放心它的正确性。

设 a,b 要进行有交并,先将a以小于等于b中最小元素和大于b中最小元素分成 c,d两类,在先将b以小于等于d中最小元素和大于d中最小元素分成 e,f两类,把a,e,d合并,b设置为f。重复直到值域无交,直接合并完事。

请问这样实现有交并复杂度是能保证的吗?

2024/4/11 08:50
加载中...