二次离线莫队学习笔记
二次离线莫队
对于普通莫队，时间复杂度为 \(O(N\sqrt{M})\) 乘以每次增加、删除操作的时间复杂度，一般为 \(O(1)\)。其不为 \(O(1)\) 时，但满足增加或删除操作其中至少有一个为 \(O(1)\) 时，我们也可以用回滚莫队 \(O(N\sqrt{M})\) 实现。然而，有时两项操作均不能达到 \(O(1)\)，例如其复杂度为“区间长度”。在一些特定的题目中，我们可以使用二次离线莫队，时间复杂度还是 \(O(N\sqrt{M})\)。
在用这种方法处理区间的增加和删除操作时，变化量无法快速求出。但是我们注意到众多区间的变化量有“相似”之处，于是将这些变化量离线下来，统一算出后，再用于更新莫队的区间操作。
以Acwing2535 二次离线莫队为例。
给定一个长度为 \(n\) 的序列 \(a1,a2,…,an\) 以及一个整数 \(k\)。
现在要进行 \(m\) 次询问，每次询问给定一个区间 \([l,r]\)，请你求出共有多少个数对 \((i,j)\) 满足 \(l≤i
\(1≤n,m≤10^5\)，\(1≤k≤14\)，\(0≤a_i<2^{14}\)。
注意到，区间左右端点指针的每次移动的时间复杂度均为“当前区间长度”，显然无法通过此题。我们来看二次离线莫队的做法。
首先，设 \(tar\) 为一个二进制下有 \(k\) 个 \(1\) 的数。我们定义 \(x⊕y=tar\) 为 \(x\) 与 \(y\) 匹配。另外，若 \(x⊕y=tar\)，则 \(y=tar⊕x\)。由于 \(k≤14\)，\(a_i<2^{14}\)，故所有的 \(tar\) 均可以预处理得出，且总数不到3500个。其个数设为 \(S\)。
设 \(f(i)\) 表示 \(1\)~\(i\) 中与 \(w_{i+1}\) 匹配的数的个数。再利用一个迭代数组 \(g(x)\) 表示迭代过程中与 \(x\) 匹配的数的个数。则可以 \(O(NS)\) 求出：
for (int i = 0; i < 1 << 14; i++) {
int x = i, cnt = 0;
while (x) {
cnt++; x ^= x & -x;
}
if (cnt == k) tar.push_back(i); //求tar
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j < tar.size(); j++) g[w[i] ^ tar[j]]++;
f[i] = g[w[i + 1]];
}
再来看莫队中区间的增减操作：
- 将区间右指针 \(R\) 向右移动到 \(r\)
将 \(R\) 移动到 \(R+1\) 时，\(res\) += \([L,R]\) 与 \(w_{R+1}\) 匹配的数的个数。利用前缀和的思想，就是 \([1,R]\) 与 \(w_{R+1}\) 匹配个数 - \([1,L-1]\) 与 \(w_{R+1}\) 匹配个数。前者 = \(f(R)\)，且随 \(R\) 向右移动 \(i\) 位，分别为 \(f(R+i)\)。后者分别为 \([1,L-1]\) 与 \(w_{R+i}\) 匹配个数。
于是得到，\(R\) 右移至 \(r\)，\(res\) += $ \sum_{i=R}^{r-1} f(i)$ - \([1,L-1]\) 与 \([r+1,R]\) 匹配个数。将后项记作 \(match([1,L-1],[R+1,r])\)。
此时，前项可随指针右移快速求出，但后项仍无法快速求出。没关系，先看其他情况。 - 将 \(R\) 向左移动到 \(r\)
推法与上相似。\(res\) += \((- \sum_{i=r}^{R-1} f(i))+match([1,L-1],[r+1,R])\)。 - 将 \(L\) 向左移动到 \(l\)
将 \(L\) 移动到 \(L-1\) 时，\(res\) += \([L,R]\) 与 \(w_{L-1}\) 匹配个数。即 \([1,R]\) 与 \(w_{L-1}\) 匹配个数 - \([1,L-1]\) 与 \(w_{L-1}\) 匹配个数。因为 \(w_{L-1}\) 与自己匹配当且仅当 \(k=0\)，故后项可化为 \(f(L-2)+!k\)。于是得到，\(L\) 左移至 \(l\)，\(res\) += \((- \sum_{i=l-1}^{L-2} (f(i)+!k)) + match([1,R],[l,L-1])\)。 - 将 \(L\) 向右移动到 \(l\)
与上相似。\(res\) += \(\sum_{i=L-1}^{l-2} (f(i)+!k) - match([1,R],[L,l-1])\)。
于是我们的任务只剩下快速求出所有 \(match\)。如果在移动时在线模拟，那么复杂度很高。但是我们注意到所有 \(match\) 有相似之处，它们都形如 \(match([1,x],[a,b])\)。那么我们是不是可以将它们全部离线下来，扫一边序列的同时，利用迭代数组 \(g\) 统一求出所有 \(match\) 呢？很显然，这样的做法避免了每次求 \(match\) 时重新从头扫描，时间复杂度肯定可以降低。那么我们来分析一下做法。
扫描一遍序列，并实时更新迭代数组 \(g\)。来到第 \(x\) 个数时，找到所有 \(match([1,x],[a,b])\)，记录答案为 \(\sum_{i=a}^b g(i)\)。总时间复杂度为 \(O(NS+LEN)\)，其中 \(LEN\) 表示所有 \(match\) 的 \(b-a\) 长度之和。我们考虑 \(b-a\) 的实际意义，就是：指针 \(L\) 和 \(R\) 的移动距离之和！在普通莫队中，这个值就是莫队的时间复杂度 \(O(N\sqrt{M})\)。可以承受。
至此，二次离线莫队的算法已经分析完了。因为 \(S\) 较小，故时间复杂度为 \(O(N\sqrt{M})\)。
Code
#include
#include
#include
#include
#include
#define ll long long
using namespace std;
const int N = 1e5 + 5;
int n, m, k, w[N], pos[N];
int g[N], f[N];
ll ans[N];
struct Query {
int id, l, r;
ll res;
bool operator <(const Query &oth) const {
return pos[l] != pos[oth.l] ? pos[l] < pos[oth.l] : r < oth.r;
}
} q[N];
vector tar;
vector range[N]; //range存储match
//注意，虽然q和range都适用Query类型，但它们的实际意义不一样
int read() {
int x = 0; char c = getchar();
while (c < '0' || c > '9') c = getchar();
while (c >= '0' && c <= '9') {x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}
return x;
}
int main() {
n = read(); m = read(); k = read();
for (int i = 1; i <= n; i++) w[i] = read();
for (int i = 0; i < 1 << 14; i++) {
int x = i, cnt = 0;
while (x) {
cnt++; x ^= x & -x;
}
if (cnt == k) tar.push_back(i);
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j < tar.size(); j++) g[w[i] ^ tar[j]]++;
f[i] = g[w[i + 1]];
}
int len = max(1, (int)sqrt((double)n * n / m));
for (int i = 1; i <= n; i++) pos[i] = (i - 1) / len + 1;
for (int i = 1; i <= m; i++) q[i] = (Query){i, read(), read()};
sort(q + 1, q + m + 1);
for (int i = 1, L = 1, R = 0; i <= m; i++) {
int l = q[i].l, r = q[i].r;
if (R < r) range[L - 1].push_back((Query){i, R + 1, r, -1}); //-1和1的类型是为了方便代码，表示-和+
while (R < r) q[i].res += f[R], R++;
if (R > r) range[L - 1].push_back((Query){i, r + 1, R, 1});
while (R > r) q[i].res -= f[R - 1], R--;
if (L < l) range[R].push_back((Query){i, L, l - 1, -1});
while (L < l) q[i].res += f[L - 1] + !k, L++;
if (L > l) range[R].push_back((Query){i, l, L - 1, 1});
while (L > l) q[i].res -= f[L - 2] + !k, L--;
}
memset(g, 0, sizeof (g));
for (int i = 1; i <= n; i++) {
for (int j = 0; j < tar.size(); j++) g[w[i] ^ tar[j]]++;
for (int j = 0; j < range[i].size(); j++)
for (int p = range[i][j].l; p <= range[i][j].r; p++)
q[range[i][j].id].res += g[w[p]] * range[i][j].res;
}
for (int i = 1; i <= m; i++) {
q[i].res += q[i - 1].res; ans[q[i].id] = q[i].res;
}
for (int i = 1; i <= m; i++) printf("%lld\n", ans[i]);
return 0;
}
In the end
本题要旨在于巧妙的前缀和转化，以及 \(f\) 和 \(g\) 数组的实现。