题意
有一个无限长的字符串 $s$，其中 $s_i = \operatorname{popcount}\left(i\right)$
给定 $n$ 个区间 $\left[l_i, r_i\right]$，令字符串 $S = s_{l_1\ldots r_1} + \cdots + s_{l_n\ldots r_n}$。
$q$ 次询问，每次查询一个 01 串 $t_i$ 在 $S$ 中的出现次数。
$1 \leq n, q \leq 10^5, 1 \leq l_i \leq r_i \leq 10^9, \sum \lvert T_i\rvert \leq 5 \times 10^5$
题解
如果 $S$ 长度很小，我们可以把所有 $t_i$ 建一个 AC 自动机，然后在上面跑 $S$。维护一个数组 $v$，每次跑到一个点 $x$，把 $v_x$ 加上 $1$。
$t_i$ 的答案即为 Fail 树上 $t_i$ 子树中 $v$ 的和。
注意到，建 AC 自动机和求答案是 $\Theta \left(\sum \lvert T_i\rvert\right)$ 的，但是在 AC 自动机上跑 $S$ 是 $\Theta \left(\lvert S \rvert\right)$ 的，无法接受，所以需要加速跑 $S$ 的过程。
接下来，我们看一看 $s$ 长什么样：
$\tt011010011001011010010110011010011$
我们可以使用如下递推式来生成 $s$：
初始时 $s = \tt0$，$s = s + s'$，其中 $s'$ 表示 $s$ 01 翻转后的字符串。
即每次把 $s$ 01 翻转后的字符串拼接到 $s$ 后面。
令 $T_k = s_{0 \ldots 2^k -1}$，即 $T_k$ 为 $s$ 的前 $2_k - 1$ 个字符组成的字符串。
这样，我们可以把 $S$ 拆成 $\Theta\left(\log \lvert S\rvert\right)$ 个区间，每个区间都是 $T_k$ 或者 ${T'}_k$。
举个例子，$\tt01011010010110$ 就可以拆成 $T_1 + T_2 + {T'}_3$。
同样的，我们也可以用递推的方式生成 $T_k$：$T_k = T_{k - 1} + {T'}_{k - 1}$
现在，$S$ 由 $\Theta\left(\lvert S\rvert \log \lvert S\rvert\right)$ 段 $T_k$ 拼接而成。
考虑使用如下方式快速跑 $T_k$：
设 $f\left(x, k, 0/1\right)$ 表示从 AC 自动机上的一点 $u$ 开始跑 $T_k/{T'}_k$，会跑到的点。
维护 $g\left(x, k, 0/1\right)$ 表示从 AC 自动机上的一点 $u$ 开始跑 $T_k/{T'}_k$，所有途经的点，的 $v$ 数组都加上 $1$。
即我们通过把 $g\left(x, k, 0/1\right)$ 加上 $1$，来代替 从 AC 自动机上的一点 $u$ 开始跑 $T_k/{T'}_k$，所有途经的点，的 $v$ 数组都加上 $1$。最后求答案的时候再还原回去。
接下来考虑快速求 $f\left(x, k, 0/1\right)$。
由于 $T_k = T_{k - 1} + {T'}_{k - 1}$，所以 $f\left(x, k, 0/1\right) = f\left(f\left(x, k - 1, 0/1\right), k - 1, 1/0\right)$，相当于先从 $x$ 开始跑一个 $T_{k - 1}$，又跑了一个 ${T'}_{k - 1}$。类似于倍增。
接下来就可以把 $f$ 处理出来，然后逐个枚举 $S$ 的每一段，然后先把 $g\left(x, k, 0/1\right)$ 加上 $1$，接着当前点 $x = f\left(x, k, 0/1\right)$。
这样 $S$ 就跑完了。
现在的问题是如何把 $g\left(x, k, 0/1\right)$ 还原到每一个点。
考虑到 $g\left(x, k, 0/1\right)$ 的贡献可以等价的推给 $g\left(\cdots, k - 1, 0/1\right)$，逐步推下去之后就可以全部推到 $g\left(\cdots, 0, 0/1\right)$ 上，就相当于是原来点的贡献了。
从 $\Theta \left(\log \lvert S \rvert\right)$ 到 $1$ 枚举 $k$，做：
$g\left(x, k - 1, 0/1\right) += g\left(x, k, 0/1\right)$
$g\left(f\left(x, k - 1, 0/1\right), k - 1, 1/0\right) += g\left(x, k, 0/1\right)$
$g\left(x, k, 0/1\right) = 0$
即可。