[分块][bitset][RMQ]区间

源自 ditoly 大爷的 FJ 省队集训模拟赛题

Statement
给定一个长度为 \(n\) 的序列 \(a\) ，有 \(m\) 次询问
每次询问给出一个 \(k\) ，再给出 \(k\) 个区间
求出原序列的这 \(k\) 个区间的并集中，出现了多少种不同的数
强制在线
\(1\le n,m,\sum k,a_i\le10^5\) ，时限 \(1\text{s}\) ，空限 \(8\text{MB}\)

第一步：主要思路
考虑使用 bitset 维护每个数是否出现过
每次询问时，可以求出给出的所有区间的 bitset 之后或起来
区间的 bitset 可以用数据结构来维护
然而用平常的方式维护显然是过不了空间的，值域分段也不能用（强制在线）

第二步：优化空间
尝试思考如何维护 bitset 才能把空间卡进 \(8\text{MB}\)
考虑把序列分成 \(64\) 块，对于任意 \(1\le l\le r\le 64\) 求出第 \(l\) 到第 \(r\) 块的 bitset
这样求一个区间的 bitset 就可以把整块的部分直接利用维护的信息，剩余的部分暴力了
但这样空间仿佛还是开不下
不过把这 \(64\) 块的区间 bitset 使用 ST 表进行维护之后，整块的 bitset 就能表示成两个 bitset 的或，这样就可以通过空间限制了
时空复杂度略

第三步：常数优化
考虑一个数，如果它在整个序列中只出现一次，那么对于这个数是否有贡献，我们只需考虑这个数在给定区间并集中的出现次数
这样对于所有的 \(1\le i\le n\) ，求出 \(is_i\) 表示 \(a_i\) 是否在整个序列中只出现一次，那么只出现一次的数的贡献就可以直接用 \(is\) 的前缀和算出来了
这样可以减少一半的常数

Code
咕咕咕

巴特西

[分块][bitset][RMQ]区间

Statement

第一步：主要思路

第二步：优化空间

第三步：常数优化

Code

最新文章

热门文章