历年各赛事真题选做
\(\newcommand \oper \operatorname\)\(\newcommand \seq \mathcal\) \(\newcommand \m \mathbf\)\(\newcommand \txt \texttt\)
\(\text{By DaiRuiChen007}\)
推荐阅读：
- A. [九省联考 2018] 秘密袭击
- E. [HNOI/AHOI2018] 寻宝游戏
A. [九省联考 2018] 秘密袭击
I. 朴素的 dp
首先，我们知道答案就是求所有联通块中的第 \(k\) 大值和
第一步转化，我们可以拆分贡献，对于每个 \(i\) 求出：连通块中第 \(k\) 大数为 \(i\) 的方案数，把方案数乘以 \(i\) 再求和即可
第二步转化，我们可以把乘以 \(i\) 的贡献拆成 \(i\) 次计算的贡献，即：对所有 \(i\)，统计连通块中的 \(k\) 大数 \(\ge i\) 的方案数，这样每个 \(i\) 恰好被计算 \(i\) 次
第三步转化，我们可以把“第 \(k\) 大数 \(\ge i\)”转化成“值 \(\ge i\) 的数 \(\ge k\) 个”的条件，即：对于所有 \(i\)，求出 \(\ge i\) 的数在连通块中出现次数 \(\ge k\) 的方案数
在转化之后，我们可以设计一个显然的 dp 来解决这个问题，用 \(f_{u,i,j}\) 表示以 \(u\) 为根的子树中值 \(\ge i\) 的数出现恰好 \(j\) 次的连通块数量
为了防止算重，我们可以强制要求 \(f_{u,i,j}\) 中统计的连通块一定包含 \(u\)，从而防止重复计算
而 \(f_{u,i,j}\) 的转移比较显然，直接从对于每个 \(u\) 的儿子 \(v\)，用 \(f_{v,i,j'}\) 以一个卷积的形式往上转移
为了更加方便统计答案，我们不妨再定义一个 \(g_{u,i,j}\) 表示所有 \(u\) 的子树中的 \(v\) 的 \(f_{v,i,j}\) 的和，即非强制选定 \(u\) 时的方案数，\(g\) 的转移比较简单，直接从 \(u\) 的所有儿子处转移 \(g\) 值并且转移 \(u\) 本身的 \(f\) 值
那么，答案就是 \(\sum_{i=1}^n\sum_{j=k}^n g_{\oper{root},i,j}\)，即对于每个 \(i\in[1,n]\)，统计选择值 \(\ge i\) 的节点，选择了 \(k\sim n\) 次的方案数再累加求和
II. 多项式技巧维护 dp
注意到 \(f\) 的转移很像对 \(j\) 一维卷积的形式，因此我们可以在 \(f_{u,i},g_{u,i}\) 中用生成函数维护所有 \(f_{u,i,j},g_{u,i,j}\) 的值
不妨假设 \(F_{u,i}=\sum_{j=0}^n f_{u,i,j}\times x^j,G_{u,i}=\sum_{j=0}^n g_{u,i,j}\times x^j\)
那么我们就把状态转移方程转化为如下的形式：
F_{u,i}&=x^{[d_u\ge i]}\prod_{v\in \oper{son}(u)} (F_{v,i}+1)\\
G_{u,i}&=F_{u,i}+\sum_{v\in\oper{son}(u)} G_{v,i}
\end{aligned}
\]
那么在这一步之后，我们把答案转化成了 \(\sum_{i=1}^n G_{\oper{root},i}\) 的 \(k\sim n\) 次项系数的和
不妨假设 \(H(x)=\sum_{i=1}^n G_{\oper{root},i}\)，那么原问题只需要我们求出 \(H(x)\) 即可解决
注意到在树上多次进行多项式乘法的复杂度较高，难以接受，因此我们考虑用用拉格朗日插值法把多项式乘法转化成普通的乘法
即，对于每个 \(x_0=1,2,3,\dots,n+1\)，我们把 \(x=x_0\) 带入所有 \(F_{u,i},G_{u,i}\) 的表达式，求出所有 \(F_{u,i},G_{u,i}\) 在 \(x=x_0\) 处的点值，从而得到 \(H(x)\) 在 \(x=x_0\) 处的点值
最终，我们通过 \(H(1)\sim H(n+1)\) 的点值运用拉格朗日插值法得到 \(H(x)\) 的系数表达，再把 \(k\sim n\) 次项的系数统计到答案中
因此，我们只需要对于每个 \(x_0\)，维护如下的转移：
F_{u,i}&=x_0^{[d_u\ge i]}\prod_{v\in \oper{son}(u)} (F_{v,i}+1)\\
G_{u,i}&=F_{u,i}+\sum_{v\in\oper{son}(u)} G_{v,i}
\end{aligned}
\]
注意，此处转移方程式中的 \(F_{u,i},G_{u,i}\) 都是数值而非多项式
III. 线段树加速转移
注意到在状态转移方程中，每个 \(i\) 对答案的实际影响很小，因此可以对于每个 \(u\)，把所有的 \(F_{u,i},G_{u,i}\) 看成两个长度为 \(n\) 的序列 \(\seq F_u,\seq G_u\) 总体维护
那么整个状态转移的过程可以拆解成如下的步骤：
- 令 \(\seq F_u[1\sim n]\gets 1\)
- 对于所有 \(i\in[1,a_u]\)，令 \(\seq F_u[i]\gets \seq F_u[i]\times x_0\)
- 枚举 \(u\) 的所有儿子 \(v\)：
- 对于所有 \(i\in [1,n]\)，令 \(\seq F_v[i]\gets \seq F_v[i]+1\)
- 对于所有 \(i\in [1,n]\)，令 \(\seq F_u[i]\gets \seq F_u[i]\times \seq F_v[i],\seq G_u[i]\gets \seq G_u[i]+\seq G_v[i]\)
- 对于所有 \(i\in[1,n]\)，令 \(\seq G_u[i]\gets \seq G_u[i]+\seq F_u[i]\)
具体的维护过程可以考虑用对于每一个节点 \(i\) 维护两个关键字 \((f,g)\)
而我们发现在序列上每一次的操作都可以表示成形如 \((f,g)\gets (a\times f+b,c\times f+g+d)\) 的形式
我们可以从矩阵乘法的角度来理解这个标记的变换，容易构造出如下的转移矩阵：
a&c&0\\
0&1&0\\
b&d&1\\
\end{bmatrix}
\times
\begin{bmatrix}
0&0&0\\
0&1&0\\
f&g&1
\end{bmatrix}
=
\begin{bmatrix}
0&0&0\\
0&1&0\\
a\times f+b&c\times f+g+d&1
\end{bmatrix}
\]
更一般地，而我们可以把任意两个转移矩阵的合并看成如下的过程：
a_2&c_2&0\\
0&1&0\\
b_2&d_2&1\\
\end{bmatrix}
\times
\begin{bmatrix}
a_1&c_1&0\\
0&1&0\\
b_1&d_1&1\\
\end{bmatrix}
=
\begin{bmatrix}
a_1\times a_2&a_1\times c_2+c_1&0\\
0&1&0\\
a_2\times b_1+b_2&c_2\times b_1+d_1+d_2&1
\end{bmatrix}
\]
注意到上面的过程等价于在原有的 \((a_1,b_1,c_1,d_1)\) 的标记上复合一个 \((a_2,b_2,c_2,d_2)\)，由于矩阵左乘的过程具有结合律，因此我们可以用线段树来维护这些 \((a,b,c,d)\) 的标记，并且 \(f=b,g=d\)
因此我们可以得到一种新的运算 \(\oplus\)：
\]
特别地，当我们只关心 \(f,g\) 的信息时，也可以写成：
\]
且 \(\oplus\) 的单位元为 \((1,0,0,0)\)，任何标记 \(\otimes\) 上这个标记依然不改变自身的值
那么我们维护 \(\seq F_u,\seq G_u\) 的每一步的过程都可以用 \(\otimes\) 的形式表示出来：
- 令 \(\seq F_u[1\sim n]\gets 1\)，等价于 \(\oplus (0,1,0,0)\)
- 对于所有 \(i\in[1,a_u]\)，令 \(\seq F_u[i]\gets \seq F_u[i]\times x_0\)，等价于 \(\otimes(x_0,0,0,0)\)
- 枚举 \(u\) 的所有儿子 \(v\)：
- 对于所有 \(i\in [1,n]\)，令 \(\seq F_v[i]\gets \seq F_v[i]+1\)，等价于 \(\otimes(1,1,0,0)\)
- 对于所有 \(i\in [1,n]\)，令 \(\seq F_u[i]\gets \seq F_u[i]\times \seq F_v[i],\seq G_u[i]\gets \seq G_u[i]+\seq G_v[i]\)，等价于 \(\otimes(\seq F_u[i],0,0,\seq G_u[i])\)
- 对于所有 \(i\in[1,n]\)，令 \(\seq G_u[i]\gets \seq G_u[i]+\seq F_u[i]\)，等价于 \(\otimes(1,0,1,0)\)
因此维护 \(\seq F_u,\seq G_u\) 的所有操作都可以写成区间 \(\otimes\) 某个标记或把两个序列对应位标记 \(\oplus\) 起来的形式
可以考虑使用线段树来优化，将这两种操作分别转化成线段树上的区间修改和合并两棵动态开点线段树，这样单次状态转移的时间复杂度就被优化到了可以接受的程度
IV. 最终处理与总结
最后，我们要在 \(\oper{root}\) 对应的线段树上查询每个节点上的标记的 \(d\) 值之和，作为对应的 \(H(x_0)\) 的值
接下来，我们只需要通过 \(H(1),H(2),\dots,H(n+1)\) 的点值还原一个 \(n\) 次多项式 \(H(x)\)
首先写出拉格朗日插值法的标准形式：
\]
然后把能够预处理的常数项提取出来，并且把可以公共计算的部分保留，从而对式子化简可得：
H(x)
&=\sum_{i=1}^{n+1} H(i)\prod_{j\ne i} \dfrac{x-j}{i-j}\\[2ex]
&=\sum_{i=1}^{n+1} \dfrac{H(i)}{\prod\limits_{j\ne i} (i-j)}\times \dfrac{\prod\limits_{j=1}^{n+1} (x-j)}{x-i}
\end{aligned}
\]
注意到：
-
系数 \(\dfrac{H(i)}{\prod\limits_{j\ne i} (i-j)}\) 可以对每个 \(i\) 用 \(\Theta(n)\) 的时间求出
-
初始多项式 \(\prod\limits_{j=1}^{n+1} (x-j)\) 直接暴力卷积可以在 \(\Theta(n^2)\) 的时间内求出
-
每次除以 \(x-i\) 的过程稍作模拟也可以用 \(\Theta(n)\) 执行单次修改
因此我们在 \(\Theta(n^2)\) 的时间复杂度内就可以插出 \(H(x)\) 的系数表达
最终，我们的总时间复杂度是 \(\Theta(n^2\log w)\)，瓶颈在枚举 \(x_0\) 并且对于每个 \(x_0\) 在树上用线段树合并维护点值
B. [IOI2022] 数字电路
首先，我们把计数问题转成概率问题，假设每个点的阈值是对应范围内的一个随机整数，用 \(f_u\) 表示此时 \(u\) 的值为 \(1\) 的概率
考虑 \(u\) 的所有儿子 \(v\in\oper{son}(u)\)，我们能求出 \(\oper{son}(u)\) 中 \(1\) 的期望数量，设 \(c_u\) 表示 \(\oper{son}(u)\) 中 \(1\) 的个数，那么：\(E(c_u)=\sum_{v\in\oper{son}(v)}f_v\)
接下来考虑如何通过 \(E(c_u)\) 推出 \(f_u\)，我们可以把 \(E(c_u)\) 按定义对于不同的 \(c_u\) 给拆开，即令 \(g_{u,i}\) 表示 \(\oper{son}(u)\) 中出现恰好 \(i\) 个 \(1\) 的概率，设 \(|\oper{son}(u)|=s_u\)，那么我们有 \(\sum_{i=1}^{s_u} i\times g_{u,i}=E(c_u)\)，这是根据期望的定义推出的
显然，为了求出 \(f_u\)，我们只需对于每个 \(i\in[1,s_u]\) 求出：当 \(\oper{son}(u)\) 中有恰好 \(i\) 个 \(1\) 时，\(u\) 的值为 \(1\) 的概率，显然，此时阈值应该 \(\le i\)，而阈值的总取值共有 \(s_u\) 种，因此此时有 \(\dfrac i{s_u}\) 的概率使得 \(u\) 的值为 \(1\)，将对应的 \(i\) 的贡献相加得到：\(f_u=\sum_{i=1}^{s_u}\dfrac i{s_u}\times g_{u,i}\)
联立两式，我们知道 \(f_u=\dfrac1{s_u}\sum_{i=1}^{s_u} i\times g_{u,i}=\dfrac{E(c_u)}{s_u}=\dfrac 1{s_u}\sum_{v\in\oper{son}(v)}f_v\)，因此我们得到了 \(f_u\) 的转移
注意到 \(f_u\) 的转移形式是线性的，因此每个叶子结点对 \(f_0\) 的贡献也是线性的，准确来说：某个叶子 \(v\) 对 \(f_0\) 的贡献是 \(\prod_{u\in\oper{path}(v,0)} \dfrac{1}{s_u}\)（忽略 \(s_u=0\) 的项，即不考虑叶子结点的贡献）
回到原来的计数问题上，某个叶子 \(v\) 对答案的贡献就是 \(\prod_{u\not\in\oper{path}(v,0)} s_u\)，直接预处理出每个叶子对答案的贡献，注意到只有值为 \(1\) 的叶子对答案有贡献，因此用线段树维护区间反转，统计（有贡献的叶子的）整体和的操作即可
注意题目给出的模数不支持求逆元，因此可能要预处理子树内的 \(s_u\) 积，再用 dfs 逐个转移出每个叶子对答案的贡献
时间复杂度 \(\Theta((m+q)\log m)\)
C. [BJOI2018]二进制
首先我们对原有的条件进行分析，注意到 \(2^{2k}\bmod 3=1,2^{2k-1}\bmod 3=2\)：
因此，对于一个二进制数 \(S\)，我们用 \(x_0\) 表示 \(S_0+S_2+S_4+\cdots\)，用 \(x_1\) 表示 \(S_1+S_3+S_5+\cdots\)，那么 \(S\equiv x_0-x_1\pmod 3\)
又因为对于一个给定的区间，无论怎么重排，\(x_0+x_1\) 总是定值，那么我们可以通过对 \(x_0+x_1\) 的分析入手：
- 当 \(x_0+x_1\bmod 2=0\)，直接使得 \(x_0=x_1\) 即可，即重排成一个形如 \(000\cdots001111\cdots1\) 的串其中串末尾恰好有偶数个 \(1\)，而相邻的两个 \(1\) 可以看成 \(2^{k+1}+2^{k}=3\times 2^k\) 的形式，因此这个数必然是 \(3\) 的倍数
- 当 \(x_0+x_1\bmod 2=1\)，由于 \(x_0-x_1\equiv x_0+x_1\equiv 1\pmod 2\) 且 \(x_0-x_1\equiv S\equiv 3\pmod 3\)，因此 \(|x_0-x_1|\) 至少是 \(3\)，因此首先要保证 \(x_0+x_1\ge 3\)，注意到我们可以构造一个形如 \(000\cdots 001111\cdots 11110101\) 的串，此时 \(x_0\) 比 \(x_1\) 多 \(3\) 个，且使用的 \(0\) 至少 \(2\) 个，可以证明不存在仅使用一个 \(0\) 而使得 \(x_0+x_1\bmod 3=0\) 的方案
我们发现对符合条件的区间计数比较麻烦，考虑反面考虑，对满足如下两个条件至少之一的串 \(S\) 进行计数：
显然，满足这两个条件中的任意一个的都是不合法的 \(S\)，但由于这两个条件有相交部分，因此我们可以想到用容斥原理来计算，分别计算满足如下条件的 \(S\) 的数量：
- \(S\) 中有奇数个 \(1\)，且 \(0\) 的个数 \(\le 1\) 个
- \(S\) 中只有一个 \(1\)
- \(S\) 中只有一个 \(1\)，且 \(0\) 的个数 \(\le 1\) 个
算出满足条件一、二的 \(S\) 的数量再减去满足条件三的 \(S\) 的数量即可
首先解决满足条件一的 \(S\) 的数量：
先考虑一个简单的 dp，用 \(f_{i,j,k}\) 表示以 \(i\) 结尾，其中 \(1\) 的个数 \(\bmod 2\) 的余数为 \(j\)，\(0\) 的个数恰好为 \(k\) 的 \(S\) 的数量
注意到只有 \(0\le k\le 1\) 的情况有用，而我们要统计的答案为 \(F_{i}=\sum_{j\le i} f_{i,1,0}+f_{i,1,1}\) 因此我们可以写出如下的转移方程：
- 当 \(a_i=0\) 时：
f_{i,0,0}&=0\\
f_{i,0,1}&=f_{i-1,0,0}+1\\
f_{i,1,0}&=0\\
f_{i,1,1}&=f_{i-1,1,0}\\
F_{i}&=F_{i-1}+f_{i,1,0}+f_{i,1,1}=F_{i-1}+f_{i-1,1,0}
\end{cases}
\]
- 当 \(a_i=1\) 时：
f_{i,0,0}&=f_{i-1,1,0}\\
f_{i,0,1}&=f_{i-1,1,1}\\
f_{i,1,0}&=f_{i-1,0,0}+1\\
f_{i,1,1}&=f_{i-1,0,1}\\
F_i&=F_{i-1}+f_{i,1,0}+f_{i,1,1}=F_{i-1}+f_{i-1,0,0}+f_{i-1,0,1}+1
\end{cases}
\]
显然想到可以用矩阵来维护这个转移过程：
- 当 \(a_i=0\) 时：
f_{i-1,0,0}\\
f_{i-1,0,1}\\
f_{i-1,1,0}\\
f_{i-1,1,1}\\
F_{i-1}\\
1
\end{bmatrix}
\times
\begin{bmatrix}
0&0&1&0&1&0\\
0&0&0&1&1&0\\
1&0&0&0&0&0\\
0&1&0&0&0&0\\
0&0&0&0&1&0\\
0&0&1&0&1&1
\end{bmatrix}
=
\begin{bmatrix}
0\\
f_{i-1,0,0}+1\\
0\\
f_{i-1,1,0}\\
F_{i-1}+f_{i-1,1,0}\\
1
\end{bmatrix}
\]
- 当 \(a_i=1\) 时
f_{i-1,0,0}\\
f_{i-1,0,1}\\
f_{i-1,1,0}\\
f_{i-1,1,1}\\
F_{i-1}\\
1
\end{bmatrix}
\times
\begin{bmatrix}
0&0&1&0&1&0\\
0&0&0&1&1&0\\
1&0&0&0&0&0\\
0&1&0&0&0&0\\
0&0&0&0&1&0\\
0&0&1&0&1&1
\end{bmatrix}
=
\begin{bmatrix}
f_{i-1,1,0}\\
f_{i-1,1,1}\\
f_{i-1,0,0}+1\\
f_{i-1,0,1}\\
F_{i-1}+f_{i-1,0,0}+f_{i-1,0,1}+1\\1
\end{bmatrix}
\]
初始向量为 \(\begin{bmatrix}0&0&0&0&0&1\end{bmatrix}\)
同理，对于第二个条件，我们也可以做类似的分析：
设 \(g_{i,j}\) 表示以 \(i\) 结尾且其中恰好有 \(j\) 个 \(1\) 的方案数，而我们要求的是 \(G_i=\sum_{j\le i}g_{i,1}\)，可以写出如下的转移方程：
- \(a_i=0\) 时：
g_{i,0}&=g_{i-1,0}+1\\
g_{i,1}&=g_{i-1,1}\\
G_i&=G_{i-1}+g_{i,1}=G_{i-1}+g_{i-1,1}
\end{cases}
\]
- \(a_i=1\) 时：
g_{i,0}&=0\\
g_{i,1}&=g_{i-1,0}+1\\
G_i&=G_{i-1}+g_{i,1}=G_{i-1}+g_{i-1,0}+1
\end{cases}
\]
把这两个转移写成矩阵的形式就是：
- \(a_i=0\) 时：
g_{i-1,0}\\
g_{i-1,1}\\
G_i\\
1
\end{bmatrix}
\times
\begin{bmatrix}
1&0&0&0\\
0&1&1&0\\
0&0&1&0\\
0&0&0&1
\end{bmatrix}
=
\begin{bmatrix}
g_{i-1,0}+1\\
g_{i-1,1}\\
G_{i-1}+g_{i-1,1}\\
1
\end{bmatrix}
\]
- \(a_i=1\) 时：
g_{i-1,0}\\
g_{i-1,1}\\
G_i\\
1
\end{bmatrix}
\times
\begin{bmatrix}
0&1&1&0\\
0&0&0&0\\
0&0&1&0\\
0&1&1&1
\end{bmatrix}
=
\begin{bmatrix}
0\\
g_{i-1,0}+1\\
G_{i-1}+g_{i-1,0}+1\\
1
\end{bmatrix}
\]
初始向量为 \(\begin{bmatrix}0&0&0&1\end{bmatrix}\)
因此这两个条件可以看成最标准的动态 dp 的形式，用线段树维护单点修改和区间求矩阵积两种操作即可
接下来考虑第三个条件，这个条件的分析就很简单了：
- \(S\) 中只有一个 \(1\)：直接用树状数组维护一下区间内 \(1\) 的个数即可统计
- \(S\) 中有 \(1\) 个 \(1\) 和 \(1\) 个 \(0\)：对于每一对 \((a_{i-1},a_i)\)，维护 \([a_{i-1}\ne a_i]\) 作为 \(i\) 的贡献，查询只需要查询 \((l,r]\) 范围内的贡献和即可
综上所述，我们可以把所有的操作用线段树或树状数组来维护
时间复杂度 \(\Theta(\delta^3(n+q)\log n)\)，其中 \(\delta\) 为动态 dp 中转移矩阵的大小，此处 \(\delta=6\)
D. [CCC2018] 最大战略储备
首先把每个城市看成一个节点，那么所有的节点可以看成一个矩阵的形式，每个城市可以用一个二元组表示 \((i,j)\)，其中同一个星球的城市在同一行（\(i\) 相同），在星球中的相对标号相同的城市在同一列（\(j\) 相同），那么原图中的每条边一定是形如如下两种边之一：
- 对于某两行 \(x,y\)，对于所有列 \(j\)，连接 \((x,j),(y,j)\)，称作“竖边”
- 对于某两列 \(x,y\)，对于所有行 \(j\)，连接 \((i,x),(i,y)\)，称作“横边”
显然原问题等价于在矩阵中求最小生成树
考虑继续用 Kruskal 算法，按边权将所有的边从小到大排序，手动模拟几次的过程：
- 假设第一条边是横边 \((x_1,y_1)\)，那么可以直接连接所有的 \((x_1,j),(y_1,j)\)
- 假设第二条边也是横边 \((x_2,y_2)\)，那么根据 Kruskal 的定义，假如 \((x_2,y_2)\) 所在的列不连通就可以连接所有的 \((x_2,j),(y_2,j)\)
- 假设第三条边是竖边 \((x_3,y_3)\)，我们需要对所有 \((i,x_3),(i,y_3)\) 连边，但是由于有一些竖边可能会和横边构成环（例如 \((x_1,y_3)\to(x_1,y_3)\to (y_1,y_3)\to (y_1,x_3)\to(x_1,x_3)\)），观察后可以发现，每一行中的连通块，我们只需要挑一个点连接竖边
- 假设第四条边是横边 \((x_4,y_4)\)，首先我们要判断 \((x_4,y_4)\) 所在的列是否联通，然后我们要注意 \(x_4\) 和 \(y_4\) 列中同样的连通块只要连一个，因此这就和每一列的联通情况有关，容易想到一个断言：每一列的联通情况都是一样的，这是显然的，只要观察到：在第三次的过程中，没连接的竖边实际上的两个端点也是联通的，因此我们可以在此时将这条竖边看做联通的，因此对于每个列的联通情况只需要一个并查集就可以维护了
每次加入新横边的时候，连边的数量就是列的连通块数量，然后再连接对应的两个列，加入横边同理
因此我们只需要对于行和列分别维护并查集即可维护答案
时间复杂度 \(\Theta((p+q)\log(p+q))\)
E. [HNOI/AHOI2018] 寻宝游戏
首先对每个二进制位分别考虑，要注意到如下的观察
- \(0\oper{and}1=0,1\oper{and}1=1\) 以及 \(0\oper{or}0=0,1\oper{or}0=1\)，即 \(\oper{and}1\) 和 \(\oper{or} 0\) 操作不影响原数的值
- \(0\oper{and}0=0,1\oper{and}0=0\) 以及 \(0\oper{or}1=1,1\oper{or}1=1\)，即 \(\oper{and}0\) 和 \(\oper{or} 1\) 会将数值直接推平成操作数的值
显然，对于每个位最终的结果，一定是只由最后一个 \(\oper{and}0\) 或 \(\oper{or}1\) 操作确定的
我们有这样的一个构造：把一个长度为 \(n\) 的操作序列看成 01 序列 \(\seq O\)，其中 \(\oper{and}\to 1,\oper{or}\to 0\)
考虑某一位 \(i\) 上的 \(n\) 个数从小到大顺次构成的数值序列 \(\seq D_i\)，我们把操作序列和数值序列取反，发现答案的第 \(i\) 位 \(d_i=[\seq O<\seq D_i]\)，其中 \(<\) 表示比较字典序
事实上，这个观察很好理解，从后往前逐位考虑，如果最高位不同，那么 \(\seq O<\seq D_i\) 就代表最后一组操作是 \(\oper{or}1\)，此时 \(d_i=1\)，否则代表 \(\oper{and}0\)，此时 \(d_i=0\)，因此此时 \(d_i=[\seq O<\seq D_i]\) 成立
如果最高位相同，那么比较次高位，等价于最后一组操作是 \(\oper{and}1\) 或 \(\oper{or}0\)，这并不改变 \(d_i\)，因此结果依赖于倒数第二次操作后的 \(d_i\)，等价于比较次高位，如果最终 \(\seq O=\seq D_i\)，那么表示全程没有修改，\(d_i\) 直接为初值也就是 \(0\)，简单做数学归纳法即可证明这个命题的正确性
我们先预处理出每个位 \(i\) 上 \(n\) 个数从大到小逆序排列所对应的数值序列 \(\seq D_i\)，对于当前 \(r\) 的某个数位 \(i\)，\(r_i=0\) 表示 \(\seq D_i\le \seq O\)，否则表示 \(\seq D_i>\seq O\)，因此 \(\seq O\) 可以表示成 \(\seq O\in[\seq D_l,D_r)\) 的形式
注意到预处理出 \(\seq D_i\) 按字典序的排名以及 \(\seq D_i\) 作为二进制数所表示的对应的实际数值 \(\oper{int}(\seq D_i)\)，那么答案就是 \(\oper{int}(\seq D_r)-\oper{int}(\seq D_l)\)，可以直接快速计算（注意 \(\seq D_r<\seq D_l\) 时答案为 \(0\)）
注意在无下界的情况下用全 \(0\) 串代替 \(\seq D_l\)，在无上界的情况下用 \(2^{n}\)，即 \(\left(1\underbrace{000\cdots 0}_{n\text{ times}}\right)\) 代替 \(\mathcal D_r\)
时间复杂度 \(\Theta(nm\log m+qm)\)
