PTT
Submit
Submit
选择语言
正體中文
简体中文
PTT
Prob_Solve
[问题] 三维偏序(已解决)
楼主:
fatcat8127
(胖胖猫)
2019-03-11 02:59:22
先附上原题的连结(https://zerojudge.tw/ShowProblem?problemid=c571)
原先以为是改编自 BZOJ-3262 的陌上花,但仔细一看后发现数对的要求是严格的偏序。
我找到的作法是 第一维排序,第二维分治,第三维树状树组,但当使用分治法将第二维
合并时无法保证第一维保有严格递减的特性。
试着用同样的关键字去找题目,不过做法都是类似 BZOJ-3262 的陌上花
想问一下大大们都怎么做或者有什么具有区分的关键字吗?
作者:
FRAXIS
(喔喔)
2019-03-11 07:10:00
Offline, dominance counting
https://doi.org/10.1137/1.9781611973075.15
作者:
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大大 树套树做法感觉就是逆数对的二维版本
继续阅读
[问题] 一题现实中的问题
GYLin
Re: [问题] 乌龟塔问题
ddavid
[问题] 乌龟塔问题
nicknick0630
[问题] 请教 ZJ c824/c835 的01背包问题(已解决)
fatcat8127
[问题] 快速球协变换
j0958322080
[问题] 请教 zerojudge c260 的想法 (已解决)
vincent97198
[问题] UVA 10268 WA
BrunoBao
[问题] cascade如何分?
g318
[问题] LC 505 the maze ii 时间复杂度估算
sean72
Re: [问题] Paper Assignment Problem
FRAXIS
Links
booklink
Contact Us: admin [ a t ] ucptt.com