多次询问区间本质不同子序列数，强制在线。\(n,q\leqslant 10^6\)，\(\Sigma=\{0,1,\dots,25\}\)。

设 \(m=|\Sigma|\)。

考虑每次询问朴素 dp，根据贪心我们在每一个子序列第一次出现的地方计算贡献，设 \(f(i,j)\) 表示前 \(i\) 个字符，最后一个字母是 \(j\) 的子序列的方案数，特殊的让 \(f(i,m)\) 表示子序列为空的方案数。那么转移为

\[\begin{aligned} f(i,j)=\begin{cases} \sum_k f(i-1,k) & j=s_i\\ f(i-1,j) & \mathrm{otherwise} \end{cases} \end{aligned} \]

答案为 \(\sum_kf(n,k)-1\) 朴素 dp 复杂度为 \(O(nmq)\)。

考虑把转移写成矩阵形式，则

\[ans=UA_l\dots A_rV \]

其中：

\[U=\begin{pmatrix} 0 & 0 & \dots & 0 & 1 \end{pmatrix}\\ A_l=\begin{pmatrix} 1 & & 1 & & \\ & 1 & 1 & & \\ & & 1 & & \\ & & \vdots & \ddots & \\ & & 1 & & 1 \end{pmatrix}\\ V=\begin{pmatrix} 1 \\ 1 \\ \vdots \\ 1 \\ 1 \end{pmatrix} \]

其中 \(A_l\) 的主对角线和第 \(s_l\) 列为 1，其它位置为 0。

考虑这可以使用前缀积的方式快速维护，设 \(S_i\) 表示 \(A_1\dots A_i\)，\(T_i\) 表示 \(A_i^{-1}\dots A_1^{-1}\)，则答案可以表示为 \(UT_{l-1}S_rV\) 的形式。通过手动消元或者实际意义可知 \(A_i^{-1}\) 为

\[\begin{pmatrix} 1 & & -1 & & \\ & 1 & -1 & & \\ & & 1 & & \\ & & \vdots & \ddots & \\ & & -1 & & 1 \end{pmatrix} \]

这样可以做到 \(O(n+q)m^3\)。

考虑优化，我们考虑每一次右乘上 \(A_i\) 对矩阵的变化，我们发现，这相当于让第 \(s_i\) 列每个数字变成该行的和，同时我们注意到我们只在乎其乘上列向量 \(V\) 的值，即每行的和，所以我们只需要在维护矩阵的同时额外维护每行的和即可。

类似，考虑左乘 \(A_i^{-1}\) 对矩阵的变化，这相当于让每一列除了第 \(s_i\) 个元素都减去第 \(s_i\) 个元素，我们这次要求的是最后一行的每个元素的值，对每列额外维护一个列加 tag 即可每次 \(O(m)\) 更新与查询。最后的总复杂度是 \(O((n+q)m)\)。