3 solutions
-
0
首先这个题离线直接莫队即可。
然后还有另一种做法。
就是二分答案 ,然后数有多少种颜色没有在区间内出现过,即统计 在 内的个数,整体二分即可。
在线怎么搞。
莫队寄了。
然后那个二分答案的话要在线三维偏序,空间应该是2log的(如果有1log做法请指正。
出题人写的是值域分块。
记 表示第 块到第 块内值域第 块出现的颜色数,记 表示前 块内 出现的次数。
我们要知道什么?我们要知道值域第 块在 区间内出现了几个,以及 这个颜色有没有在 内出现。
后者是容易的,而前者呢。
我们用零散块内的元素去更新整块区间的 。
具体地,设整块区间为第 块到第 块,开一个 数组,若当前元素 的 且在 这几个整块内没有出现过,那就更新 ,然后给 加一。
查询时找到第 小所在的块然后枚举即可。
Information
- ID
- 277
- Time
- 3000ms
- Memory
- 512MiB
- Difficulty
- 8
- Tags
- (None)
- # Submissions
- 29
- Accepted
- 6
- Uploaded By