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

Re: [問題] ZeroJudge-c216

看板Prob_Solve (計算數學 Problem Solving)作者 (qqaa)時間5年前 (2019/04/02 23:17), 5年前編輯推噓8(8推 0噓 11→)
留言19則, 4人參與, 5年前最新討論串3/3 (看更多)
※ 引述《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
推
04/02 23:28, 5年前 , 1F
不可能只要靜態前綴和吧，他不是是要算修改後的和減掉修改
04/02 23:28, 1F
→
04/02 23:28, 5年前 , 2F
後會爆掉的人數乘以十萬
04/02 23:28, 2F
→
04/02 23:32, 5年前 , 3F
有靜態前綴和K就可以算出不考慮爆的答案，BST算有幾個爆掉
04/02 23:32, 3F
→
04/02 23:33, 5年前 , 4F
基本上和 GYLin 的想法是一樣的，不過預處理的時候不需要
04/02 23:33, 4F
→
04/02 23:33, 5年前 , 5F
知道詢問會有什麼東西
04/02 23:33, 5F
改了一下文章，希望會清楚一點 ※ 編輯: stimim (104.132.150.77), 04/02/2019 23:41:19
推
04/02 23:59, 5年前 , 6F
持久化線段樹? 一開始也想用這個 不過太久沒刻(資結苦手
04/02 23:59, 6F
推
04/03 00:35, 5年前 , 7F
喔喔www我一直看成題目是區間加K,查區間和
04/03 00:35, 7F
→
04/03 11:15, 5年前 , 8F
我是用 persist BST, 要用 persist segment tree 也可以
04/03 11:15, 8F
推
04/05 01:59, 5年前 , 9F
感謝大大提供的想法。我實作離線線段樹或是主席樹的
04/05 01:59, 9F
→
04/05 01:59, 5年前 , 10F
在線查詢，記憶體耗量都超過10MB，但是有看到記憶體
04/05 01:59, 10F
→
04/05 01:59, 5年前 , 11F
落在3mb的，想問說做法也是一樣的嗎?
04/05 01:59, 11F
推
04/05 13:31, 5年前 , 12F
可以用BIT 應該會省一點
04/05 13:31, 12F
推
04/05 14:47, 5年前 , 13F
BIT要怎麼處理區間查詢？雖然他可以累計1~H之間的個數
04/05 14:47, 13F
推
04/06 00:57, 5年前 , 14F
題目不是可以轉成區間<=X的數有幾個，那再考慮把詢問離線
04/06 00:57, 14F
→
04/06 00:58, 5年前 , 15F
並且拆成[1,R]<=X的有幾個-[1,L]<=X的有幾個，接下來再對
04/06 00:58, 15F
→
04/06 00:59, 5年前 , 16F
這種詢問從小到大排序，就可以用BIT計算了
04/06 00:59, 16F
推
04/06 11:23, 5年前 , 17F
感謝oT大大的說明，我以為BIT可以實現在線查詢，如果
04/06 11:23, 17F
→
04/06 11:23, 5年前 , 18F
是離線，記憶體都耗在儲存查詢...還是不知道2.5mb做
04/06 11:23, 18F
→
04/06 11:23, 5年前 , 19F
法@@
04/06 11:23, 19F
‣ 更多 stimim 的文章
文章代碼(AID): #1Setpm77 (Prob_Solve)
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 3 之 3 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共3篇)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 stimim 的文章
文章代碼(AID): #1Setpm77 (Prob_Solve)