分块 + bitset + ST 表.
对序列分块,用 bitset 来合并这些区间.
每一块开一个 bitset ,每次合并两个块需要 $O(\frac n w)$ 的时间,比边角部分的暴力处理劣,需要优化.
数字种类是可重复贡献的,可以用 ST 表来快速合并多个块,即设 $f(i,j)$ 表示 $[i,i+2^j-1]$ 这些块合并后的 bitset .
记块大小为 $S$ ,预处理 ST 表的时间复杂度为 $O(\frac{n^2}{Sw}\log \frac{n}{S})$ ,单次询问的时间复杂度为 $O(S+\frac{n}{w})$ .
空间复杂度为 $O(\frac{n^2}{Sw} \log \frac n S)$ .
时间和空间限制都比较紧,可以手写 bitset ,并把 $S$ 设置得稍大一点.
1 | //%std |