之前在與朋友討論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

似乎當初他表示可以用segment tree(競賽中指的那種)+hashtable做到

只有我以為原po的複雜度比朋友快嗎

你的題目和ＩＯＩ原題目不同P2 is bubble sort? https://ioi2018.jp/competition/tasks/

x_i的範圍是多少？如果是正的話應該很好處理

如果是正的話會有什麼特別的性質嗎？好奇

如果K值是定值 然後x_i又是正的 那麼每個值只會增加 超過K之後就可以不用考慮用線段樹維護區間最大值(小於K的最大值) 跟 等於K的數量當最大值大於等於K之後 便排除在外 並更新區間K的數量每次query可以考慮 左邊區間 更新區間 跟 右邊區間左右都是O(logn) 更新最差O(nlogn) 但是每個數只會超過一次 均攤後是O(logn)

對耶，滿有道理的XD不過還是想做整個Z上的QQ

矩形覆蓋(?) 畢竟原題裡轉化完之後K=1

我只注意到括號，沒發現一個log一個根號，我眼殘