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