之前在与朋友讨论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一个根号，我眼残