之前看过学长转载的博客,发现这样复杂度是 O(nlognlogV)O(n\log n\log V)O(nlognlogV)的,不过这篇博客并没有细说实现方式。
我自己编了一个实现方式,在几道题目上都能通过,不过还是不太放心它的正确性。
设 a,b 要进行有交并,先将a以小于等于b中最小元素和大于b中最小元素分成 c,d两类,在先将b以小于等于d中最小元素和大于d中最小元素分成 e,f两类,把a,e,d合并,b设置为f。重复直到值域无交,直接合并完事。
请问这样实现有交并复杂度是能保证的吗?