手生的很。
不过这次实际是我偷懒，正解想到了，不敢写。
题意#
求一个数组区间内，满足和是 \(m\) 倍数的子序列的数量，模 \({10}^9 + 7\)。
思路#
- \(m\) 不大，一个区间内所有子序列的和对 \(m\) 取模所有情况的数量可以放在一个向量 \(\mathbf{v}\) 里（这里注意“空序列”也被认作答案）
- 可以离线
- 区间固定后，内部的序和所需要的信息无关
- \(a_i\) 的值可直接对 \(m\) 取模
- 可以把在一个区间增加一个 \(a_i\) 的操作，转为把已知信息的向量 \(\mathbf{v}\) 乘一个矩阵
你发现你想多了- 一个区间增加一个值可以 \(\mathcal{O}(m)\) 修改
- 两个区间的信息可以 \(\mathcal{O}(m^2)\) 合并，但是只需要模 \(m\) 为 \(0\) 的信息则可以 \(\mathcal{O}(m)\) 时间内获取
弯路（可略过）#
于是可以有很多种做法，比如线段树维护这些信息。甚至可以用离线+并查集：
将询问离线，以右端点升序排序。\(a_i\) 按 \(i\) 升序往并查集里面插入。并查集保持父亲的标号大于当前点，每个点存下标从自己到父亲之间的信息。路径压缩即两个相邻的区间进行合并；集合合并即增加了一个 \(a_i\)，\(i\) 节点向 \(i + 1\) 合并，并在 \(i\) 节点保存区间的信息。
复杂度应该是 \(\mathcal{O}\left(\left(n + q\right) m^2 \alpha\left(n\right)\right)\)，超时了。
题解#
正解：离线+分治。
对区间 \([1, n]\) 进行分治，设当前处理到区间 \([l, r)\)，询问存储在集合 \(S\) 中，记 \(mid = \frac{l + r}{2}\)。
若询问为空，不用处理。
若 \(r - l \le 1\)，说明询问区间的长度都为 \(1\)，很容易处理（答案不要漏算空序列的情况）。
将询问分为“右端点小于 \(mid\)”、“左端点大于或等于 \(mid\)”、“其它”三个部分。第一个部分可以分治给 \([l, mid)\) 处理，第二个部分可以分治给 \([mid, r)\) 处理。其它情况，说明询问的两个端点跨过了 \(mid\)。
那么对于询问区间 \([u, v]\) 的信息，可以分为 \([u, mid), [mid, v]\) 两部分。因为 \(mid\) 当前是固定的，考虑从 \(mid\) 向 \(l\) 维护后缀的信息，从 \(mid\) 向 \(r\) 维护前缀的信息，这些信息可以如思路中说的 \(\mathcal{O}\left(m * \left(r - l\right)\right)\) 维护。对于每个询问，由于只需要模 \(m\) 为 \(0\) 的信息，可以在 \(\mathcal{O}(m)\) 的时间内得到解。
总时间复杂度 \(\mathcal{O(n m \log{n} + q \log{n} + q m)}\)。
评论