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

[問題] 序列中k出現的次數

看板Prob_Solve (計算數學 Problem Solving)作者 (屁孩)時間6年前 (2018/09/27 23:35), 6年前編輯推噓3(3推 0噓 15→)
留言18則, 5人參與, 6年前最新討論串1/1
之前在與朋友討論IOI 2018 P2時，對方表示以下的問題可以O((N+Q) log N)解決 但是我想了一段時間都只有想到簡單的分塊O(N+Q sqrt(N))的做法 而且最近又遇不到他，只好來詢問看看大家 題目內容： 給定一個長度為N的序列、Q次操作與一定值K，每次操作是將[L_i, R_i]加上x_i，請在每 次修改後回答整個序列中有幾項為K 如果上面被簡單解決了，不知道有沒有人要討論 若K是每次詢問才給定的情況，甚至是每次還要回答不同區間為K的有幾項 該如何做呢XD -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.193.102.192 ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1538062542.A.8AB.html
→
09/27 23:37, 6年前 , 1F
似乎當初他表示可以用segment tree(競賽中指的那種)+hash
09/27 23:37, 1F
→
09/27 23:37, 6年前 , 2F
table做到
09/27 23:37, 2F
推
09/28 08:31, 6年前 , 3F
只有我以為原po的複雜度比朋友快嗎
09/28 08:31, 3F
若N, Q皆為10^5~10^6左右，O((N+Q) log N)比較快吧
→
09/28 09:39, 6年前 , 4F
你的題目和ＩＯＩ原題目不同
09/28 09:39, 4F
→
09/28 09:41, 6年前 , 5F
09/28 09:41, 5F
IOI P2是Seats，不過我們後來算是在討論衍生的問題OAO ※ 編輯: oToToT (210.71.78.252), 09/28/2018 14:25:36
推
09/29 02:31, 6年前 , 6F
x_i的範圍是多少？
09/29 02:31, 6F
→
09/29 02:37, 6年前 , 7F
如果是正的話應該很好處理
09/29 02:37, 7F
→
09/29 12:10, 6年前 , 8F
如果是正的話會有什麼特別的性質嗎？好奇
09/29 12:10, 8F
→
09/29 12:42, 6年前 , 9F
如果K值是定值 然後x_i又是正的 那麼每個值只會增加 超過K
09/29 12:42, 9F
→
09/29 12:43, 6年前 , 10F
之後就可以不用考慮
09/29 12:43, 10F
→
09/29 12:43, 6年前 , 11F
用線段樹維護區間最大值(小於K的最大值) 跟 等於K的數量
09/29 12:43, 11F
→
09/29 12:46, 6年前 , 12F
當最大值大於等於K之後 便排除在外 並更新區間K的數量
09/29 12:46, 12F
→
09/29 12:47, 6年前 , 13F
每次query可以考慮 左邊區間 更新區間 跟 右邊區間
09/29 12:47, 13F
→
09/29 12:48, 6年前 , 14F
左右都是O(logn) 更新最差O(nlogn) 但是每個數只會超過一
09/29 12:48, 14F
→
09/29 12:48, 6年前 , 15F
次 均攤後是O(logn)
09/29 12:48, 15F
→
09/29 21:46, 6年前 , 16F
對耶，滿有道理的XD不過還是想做整個Z上的QQ
09/29 21:46, 16F
→
09/30 12:37, 6年前 , 17F
矩形覆蓋(?) 畢竟原題裡轉化完之後K=1
09/30 12:37, 17F
推
09/30 15:00, 6年前 , 18F
我只注意到括號，沒發現一個log一個根號，我眼殘
09/30 15:00, 18F
‣ 更多 oToToT 的文章
文章代碼(AID): #1RhFZEYh (Prob_Solve)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 oToToT 的文章
文章代碼(AID): #1RhFZEYh (Prob_Solve)