作者fatcat8127 (胖胖猫)
看板Prob_Solve
标题[问题] 三维偏序
时间Mon Mar 11 02:59:22 2019
先附上原题的连结(
https://zerojudge.tw/ShowProblem?problemid=c571)
原先以为是改编自 BZOJ-3262 的陌上花，但仔细一看後发现数对的要求是严格的偏序。
我找到的作法是 第一维排序，第二维分治，第三维树状树组，但当使用分治法将第二维
合并时无法保证第一维保有严格递减的特性。
试着用同样的关键字去找题目，不过做法都是类似 BZOJ-3262 的陌上花
想问一下大大们都怎麽做或者有什麽具有区分的关键字吗?
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 140.113.208.164
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1552244364.A.8E4.html
1F：推 FRAXIS: Offline, dominance counting 03/11 07:10
3F：推 oToToT: 在分治的时候强迫切点一定要是x1,x2(x1!=x2)之间就好，复 03/11 17:53
4F：→ oToToT: 杂度还会是好的，因为你最多还是长出一棵深度logN的树，每 03/11 17:53
5F：→ oToToT: 层操作总复杂度还是NlogN 03/11 17:53
6F：推 oToToT: 或者直接暴力树套树应该也会过 03/11 17:56
9F：→ fatcat8127: 感谢oToToT大大 树套树做法感觉就是逆数对的二维版 03/12 01:22
10F：→ fatcat8127: 本 03/12 01:22