- 源自 ditoly 大爷的 FJ 省队集训模拟赛题
Statement
-
给定一个长度为 (n) 的序列 (a) ，有 (m) 次询问
-
每次询问给出一个 (k) ，再给出 (k) 个区间
-
求出原序列的这 (k) 个区间的并集中，出现了多少种不同的数
-
强制在线
-
(1le n,m,sum k,a_ile10^5) ，时限 (1 ext{s}) ，空限 (8 ext{MB})
第一步：主要思路
-
考虑使用 bitset 维护每个数是否出现过
-
每次询问时，可以求出给出的所有区间的 bitset 之后或起来
-
区间的 bitset 可以用数据结构来维护
-
然而用平常的方式维护显然是过不了空间的，值域分段也不能用（强制在线）
第二步：优化空间
-
尝试思考如何维护 bitset 才能把空间卡进 (8 ext{MB})
-
考虑把序列分成 (64) 块，对于任意 (1le lle rle 64) 求出第 (l) 到第 (r) 块的 bitset
-
这样求一个区间的 bitset 就可以把整块的部分直接利用维护的信息，剩余的部分暴力了
-
但这样空间仿佛还是开不下
-
不过把这 (64) 块的区间 bitset 使用 ST 表进行维护之后，整块的 bitset 就能表示成两个 bitset 的或，这样就可以通过空间限制了
-
时空复杂度略
第三步：常数优化
-
考虑一个数，如果它在整个序列中只出现一次，那么对于这个数是否有贡献，我们只需考虑这个数在给定区间并集中的出现次数
-
这样对于所有的 (1le ile n) ，求出 (is_i) 表示 (a_i) 是否在整个序列中只出现一次，那么只出现一次的数的贡献就可以直接用 (is) 的前缀和算出来了
-
这样可以减少一半的常数
Code
- 咕咕咕