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

[oToToT (屁孩)]

之前在與朋友討論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
→ oToToT: 似乎當初他表示可以用segment tree(競賽中指的那種)+hash
→ oToToT:  table做到
推 alan23273850: 只有我以為原po的複雜度比朋友快嗎
若N, Q皆為10^5~10^6左右，O((N+Q) log N)比較快吧
→ Leon: 你的題目和ＩＯＩ原題目不同
→ Leon: P2 is bubble sort? https://ioi2018.jp/competition/tasks/
IOI P2是Seats，不過我們後來算是在討論衍生的問題OAO
※ 編輯: oToToT (210.71.78.252), 09/28/2018 14:25:36
推 idiont: x_i的範圍是多少？
→ idiont: 如果是正的話應該很好處理
→ oToToT: 如果是正的話會有什麼特別的性質嗎？好奇
→ idiont: 如果K值是定值 然後x_i又是正的 那麼每個值只會增加 超過K
→ idiont: 之後就可以不用考慮
→ idiont: 用線段樹維護區間最大值(小於K的最大值) 跟 等於K的數量
→ idiont: 當最大值大於等於K之後 便排除在外 並更新區間K的數量
→ idiont: 每次query可以考慮 左邊區間 更新區間 跟 右邊區間
→ idiont: 左右都是O(logn) 更新最差O(nlogn) 但是每個數只會超過一
→ idiont: 次 均攤後是O(logn)
→ oToToT: 對耶，滿有道理的XD不過還是想做整個Z上的QQ
→ edisonhello: 矩形覆蓋(?) 畢竟原題裡轉化完之後K=1
推 alan23273850: 我只注意到括號，沒發現一個log一個根號，我眼殘