所以这个题场上没写出来就是完全蠢了吧……
而且为啥加了各种优化还是跑不过最优解……
题意简述
给定一个长 $n$ 的整数序列, $m$ 次询问,每次给定 $k_i$ 个区间 $[i_{i,j},r_{i,j}]$ ,求这些区间中一共出现了多少种不同的数字。
部分数据强制在线。 $1\le n,m,a_i,\sum k_i\le 10^5$ 。
ML : 8MiB, TL : 1000ms.
主要思路
对序列分块。设分成 $K$ 块。
考虑如何记录答案。一个比较显然的想法是对每个块记录一个 bitset 来表示这个块有哪些数,询问就暴力把所有块或起来。
这样做出一个总时间复杂度 $O(n(\dfrac{nK}{\omega}+\dfrac{n}{K}))$ ,空间复杂度 $O(K\dfrac{n}{\omega})$ 的垃圾,然后跑得比暴力还慢。
然后发现可以用 $K^2$ 个 bitset 来维护两个块之间有哪些数,时间复杂度 $O(\dfrac{n^2}{K})$ 但是空间 $O(K^2\dfrac{n}{\omega})$ 。发现如果这样 $K$ 只能开几十,然后也跑得慢得一批。
考虑如何保持快速求出两个块之间答案的同时减少需要的空间。接下来就是本题最神仙的思路:可以使用一个ST表来维护两个块之间的答案。
这样总时间复杂度变为 $O(n(\dfrac{n}{\omega}+\dfrac{n}{K}))$ ,空间复杂度降至 $O(\dfrac{n}{\omega}\times K\log_2 K)$ , $K$ 可以开到一百,手写个 bitset 大概就能过了。
参考代码
主要有两个优化:
首先, $k_i$ 个区间先排个序,然后取并集,再把并集分成互不相交的若干个区间来做,具体详见代码。
其次,可以把序列中只出现一次的数丢出来做一个前缀和,不加到 bitset 里,询问一个区间把前缀和直接加到答案。这样 bitset 的长度减小到原来的 $\dfrac{1}{2}$ 。
1 |
|