作者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/cn.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