作者stimim (qqaa)
看板Prob_Solve
標題Re: [問題] ZeroJudge-c216
時間Tue Apr 2 23:17:02 2019
※ 引述《GYLin (Lynx)》之銘言:
: 大致策略:
: 1. 把途中所有累積加值都模100000, 原因很明顯
: 2. 當需要計算Sum[L,R]時, 其值為"不考慮爆掉的原本加總"扣掉100000*(區間內爆掉人數)
: 爆掉人數為: 區間內的Ai個數, 其值加上目前累積加值會超過100000的人們
: 要計算爆掉人數, 只要維護一個 Map[i][j] 就可以,
: Map[i][j] 就是 陣列 1~i, 加上高度 j 會爆掉的人數,
: 若開普通陣列可能需要 100000*100000 的大小,
: 但實際上出現的詢問只會有 10^6 種,
: 所以先把詢問全部存起來後, 再針對會出現的詢問求出爆掉人數,
: 再回去把存起來的詢問解決即可.
另一種可以 online 的作法(不用預處理詢問)
在每次的詢問,
假設不會爆掉,我們只要知道原始的 aL + ... + aR 再加上 K * (R - L + 1) 就是
答案。這個部份只要先算出原始 a_i 的前綴和就可以做到。
而每爆掉一個,答案就需要減掉 10^5,
因此我們想知道 aL ~ aR 中高度不超過 10^5 - K 的有幾個。
假設我們有一個 binary search tree, 裡面的點是 {i | ai <= 10^5 - K}
那我們可以在 O(lg n) 的時間知道 |{i | ai <= 10^5 - K} ∩{L...R}|
問題是我們要做出 10^5 個 BST,這樣好像會 OOM 或 TLE
再想一下會發現:
BST[0] = empty tree
BST[i] = BST[i - 1] + {j | aj == i}
也就是從 BST[0] 到 BST[10^5] ,只會有 n 個 insert
如果我們做 copy on write 的話,我們可以讓每次的 insert 都只多用 O(lg n) 的空間,
時間也還是 O(lg n)
於是,我們有:
time complexity of pre-processing: O(n lg n)
space complexity: O(n lg n)
Time complexity of each query: O(lg n) + O(1) (BST query + prefix sum)
Overall time complexity: O(m lg n + n lg n)
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 104.132.150.77
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1554218224.A.1C7.html
推 oToToT: 不可能只要靜態前綴和吧,他不是是要算修改後的和減掉修改 04/02 23:28
→ oToToT: 後會爆掉的人數乘以十萬 04/02 23:28
→ stimim: 有靜態前綴和K就可以算出不考慮爆的答案,BST算有幾個爆掉 04/02 23:32
→ stimim: 基本上和 GYLin 的想法是一樣的,不過預處理的時候不需要 04/02 23:33
→ stimim: 知道詢問會有什麼東西 04/02 23:33
改了一下文章,希望會清楚一點
※ 編輯: stimim (104.132.150.77), 04/02/2019 23:41:19
推 GYLin: 持久化線段樹? 一開始也想用這個 不過太久沒刻(資結苦手 04/02 23:59
推 oToToT: 喔喔www我一直看成題目是區間加K,查區間和 04/03 00:35
→ stimim: 我是用 persist BST, 要用 persist segment tree 也可以 04/03 11:15
推 fatcat8127: 感謝大大提供的想法。我實作離線線段樹或是主席樹的 04/05 01:59
→ fatcat8127: 在線查詢,記憶體耗量都超過10MB,但是有看到記憶體 04/05 01:59
→ fatcat8127: 落在3mb的,想問說做法也是一樣的嗎? 04/05 01:59
推 GYLin: 可以用BIT 應該會省一點 04/05 13:31
推 fatcat8127: BIT要怎麼處理區間查詢?雖然他可以累計1~H之間的個數 04/05 14:47
推 oToToT: 題目不是可以轉成區間<=X的數有幾個,那再考慮把詢問離線 04/06 00:57
→ oToToT: 並且拆成[1,R]<=X的有幾個-[1,L]<=X的有幾個,接下來再對 04/06 00:58
→ oToToT: 這種詢問從小到大排序,就可以用BIT計算了 04/06 00:59
推 fatcat8127: 感謝oT大大的說明,我以為BIT可以實現在線查詢,如果 04/06 11:23
→ fatcat8127: 是離線,記憶體都耗在儲存查詢...還是不知道2.5mb做 04/06 11:23
→ fatcat8127: 法@@ 04/06 11:23