[问题] 三维偏序(已解决)

楼主: fatcat8127 (胖胖猫)   2019-03-11 02:59:22
先附上原题的连结(https://zerojudge.tw/ShowProblem?problemid=c571)
原先以为是改编自 BZOJ-3262 的陌上花,但仔细一看后发现数对的要求是严格的偏序。
我找到的作法是 第一维排序,第二维分治,第三维树状树组,但当使用分治法将第二维
合并时无法保证第一维保有严格递减的特性。
试着用同样的关键字去找题目,不过做法都是类似 BZOJ-3262 的陌上花
想问一下大大们都怎么做或者有什么具有区分的关键字吗?
作者: FRAXIS (喔喔)   2019-03-11 07:10:00
作者: oToToT (屁孩)   2019-03-11 17:53:00
在分治的时候强迫切点一定要是x1,x2(x1!=x2)之间就好,复杂度还会是好的,因为你最多还是长出一棵深度logN的树,每层操作总复杂度还是NlogN或者直接暴力树套树应该也会过同样贴份分治的AC Code:https://goo.gl/r5wxaj跟一份随意写的树套树: https://goo.gl/3dSE13
楼主: fatcat8127 (胖胖猫)   2019-03-12 01:22:00
感谢oToToT大大 树套树做法感觉就是逆数对的二维版本

Links booklink

Contact Us: admin [ a t ] ucptt.com