作者oToToT (屁孩)
看板Prob_Solve
標題[問題] 序列中k出現的次數
時間Thu Sep 27 23:35:39 2018
之前在與朋友討論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://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1538062542.A.8AB.html
1F：→ oToToT: 似乎當初他表示可以用segment tree(競賽中指的那種)+hash09/27 23:37
2F：→ oToToT: table做到09/27 23:37
3F：推 alan23273850: 只有我以為原po的複雜度比朋友快嗎09/28 08:31
若N, Q皆為10^5~10^6左右，O((N+Q) log N)比較快吧
4F：→ Leon: 你的題目和ＩＯＩ原題目不同09/28 09:39
IOI P2是Seats，不過我們後來算是在討論衍生的問題OAO
※ 編輯: oToToT (210.71.78.252), 09/28/2018 14:25:36
6F：推 idiont: x_i的範圍是多少？ 09/29 02:31
7F：→ idiont: 如果是正的話應該很好處理 09/29 02:37
8F：→ oToToT: 如果是正的話會有什麼特別的性質嗎？好奇 09/29 12:10
9F：→ idiont: 如果K值是定值 然後x_i又是正的 那麼每個值只會增加 超過K 09/29 12:42
10F：→ idiont: 之後就可以不用考慮 09/29 12:43
11F：→ idiont: 用線段樹維護區間最大值(小於K的最大值) 跟 等於K的數量 09/29 12:43
12F：→ idiont: 當最大值大於等於K之後 便排除在外 並更新區間K的數量 09/29 12:46
13F：→ idiont: 每次query可以考慮 左邊區間 更新區間 跟 右邊區間 09/29 12:47
14F：→ idiont: 左右都是O(logn) 更新最差O(nlogn) 但是每個數只會超過一 09/29 12:48
15F：→ idiont: 次 均攤後是O(logn) 09/29 12:48
16F：→ oToToT: 對耶，滿有道理的XD不過還是想做整個Z上的QQ 09/29 21:46
17F：→ edisonhello: 矩形覆蓋(?) 畢竟原題裡轉化完之後K=1 09/30 12:37
18F：推 alan23273850: 我只注意到括號，沒發現一個log一個根號，我眼殘 09/30 15:00