PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] 三維偏序

看板Prob_Solve (計算數學 Problem Solving)作者 (胖胖貓)時間5年前 (2019/03/11 02:59), 編輯推噓3(3推 0噓 7→)
留言10則, 3人參與, 5年前最新討論串1/1
先附上原題的連結(https://zerojudge.tw/ShowProblem?problemid=c571) 原先以為是改編自 BZOJ-3262 的陌上花，但仔細一看後發現數對的要求是嚴格的偏序。 我找到的作法是 第一維排序，第二維分治，第三維樹狀樹组，但當使用分治法將第二維 合併時無法保證第一維保有嚴格遞減的特性。 試著用同樣的關鍵字去找題目，不過做法都是類似 BZOJ-3262 的陌上花 想問一下大大們都怎麼做或者有什麼具有區分的關鍵字嗎? -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.113.208.164 ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1552244364.A.8E4.html
推
03/11 07:10, 5年前 , 1F
Offline, dominance counting
03/11 07:10, 1F
→
03/11 07:10, 5年前 , 2F
03/11 07:10, 2F
推
03/11 17:53, 5年前 , 3F
在分治的時候強迫切點一定要是x1,x2(x1!=x2)之間就好，複
03/11 17:53, 3F
→
03/11 17:53, 5年前 , 4F
雜度還會是好的，因為你最多還是長出一棵深度logN的樹，每
03/11 17:53, 4F
→
03/11 17:53, 5年前 , 5F
層操作總複雜度還是NlogN
03/11 17:53, 5F
推
03/11 17:56, 5年前 , 6F
或者直接暴力樹套樹應該也會過
03/11 17:56, 6F
→
03/11 22:45, 5年前 , 7F
同樣貼份分治的AC Code:https://goo.gl/r5wxaj
03/11 22:45, 7F
→
03/11 22:54, 5年前 , 8F
跟一份隨意寫的樹套樹: https://goo.gl/3dSE13
03/11 22:54, 8F
→
03/12 01:22, 5年前 , 9F
感謝oToToT大大 樹套樹做法感覺就是逆數對的二維版
03/12 01:22, 9F
→
03/12 01:22, 5年前 , 10F
本
03/12 01:22, 10F
‣ 更多 fatcat8127 的文章
文章代碼(AID): #1SXLwCZa (Prob_Solve)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 fatcat8127 的文章
文章代碼(AID): #1SXLwCZa (Prob_Solve)