莫队二次离线
从 \([x, y]\) 移动到 \([l, r]\)。
\(x \to l\)
查询 \(a_i\) 在区间 \([i+1, y]\) 的贡献，拆成两个前缀 \(i, y\)，预处理 \(a_{i-1}\) 对前缀 \(i-1\) 的贡献，设贡献的前缀和为 \(pre_1[i]\)。
\(x<l\)
删除 \(a_{x} \dots a_{l-1}\)。
减前缀 \(y\) 的贡献、加前缀 \(i\) 的贡献。
离线 \(\{y, x, l-1,-1\}, \Delta ans= pre_1[l] - pre_1[x]\)。
\(x>l\)
加入 \(a_l\dots a_{x-1}\)。
加前缀 \(y\) 的贡献、减前缀 \(i\) 的贡献。
离线 \(\{y, l, x-1,+1\}, \Delta ans= pre_1[l] - pre_1[x]\)。
\(y\to r\)
查询 \(a_i\) 在区间 \([x, i-1]\) 的贡献，拆成两个前缀 \(x-1, i-1\)，预处理 \(a_{i}\) 对前缀 \(i-1\) 的贡献，设贡献的前缀和为 \(pre_2[i]\)。
\(y<r\)
加入 \(a_{y+1}\dots a_r\)。
减前缀 \(x-1\) 的贡献、加前缀 \(i-1\) 的贡献。
离线 \(\{x-1, y+1, r, -1\}, \Delta ans = pre_2[r] - pre_2[y]\)。
\(y>r\)
删除 \(a_{r+1}\dots a_y\)
加前缀 \(x-1\) 的贡献、减前缀 \(i-1\) 的贡献。
离线 \(\{x-1, r+1, y, +1\}, \Delta ans = pre_2[r] - pre_2[y]\)。
离线形式 \(\{i, x, y, z\}\) 表示查询 \(a_x\dots a_y\) 对前缀 \(i\) 的贡献乘以系数 \(z\)。
计算方法和预处理方法一般是相同的，注意平衡复杂度，一般是 \(O(\sqrt n)\) 修改，\(O(1)\) 查询。
关键部分代码：
std::vector<LL> pre1(n + 1), pre2(n + 1);
for (int i = 0; i < n; i++) {
update(a[i]);
pre1[i + 1] = pre1[i] + ask(a[i]);
pre2[i + 1] = pre2[i] + ask(a[i + 1]);
}
std::sort(q.begin(), q.end());
std::vector<LL> ans(m), out(m);
std::vector<std::vector<std::array<int, 4>>> g(n + 1);
int x = 1, y = 0;
for (int i = 0; i < m; i++) {
auto [l, r, id] = q[i];
if (x < l) {
g[y].push_back({x, l - 1, -1, i});
}
if (x > l) {
g[y].push_back({l, x - 1, 1, i});
}
ans[i] += pre1[l] - pre1[x];
x = l;
if (x) {
if (y < r) {
g[x - 1].push_back({y + 1, r, -1, i});
}
if (y > r) {
g[x - 1].push_back({r + 1, y, 1, i});
}
}
ans[i] += pre2[r] - pre2[y];
y = r;
}
for (int i = 0; i <= n; i++) {
update(a[i]);
for (auto [x, y, z, id] : g[i]) {
for (int j = x; j <= y; j++) {
ans[id] += ask(a[j]) * z;
}
}
}
for (int i = 1; i < m; i++) ans[i] += ans[i - 1];
for (int i = 0; i < m; i++) out[q[i].id] = ans[i];
for (auto x : out) std::cout << x << "\n";回滚莫队
维护信息支持加入和回滚时使用。
同块右端点从小到大排序，右端点直接移动，左端点每次从块边界暴力移动，做完后回滚。
维护块左端点 \(now\)，然后循环开头加一句：
if (l > now) {
// 清空 for (int i = now; i <= y; i++) max[a[i]] = -1, min[a[i]] = n;
now = l / T * T + T - 1;
y = now - 1;
ans = 0;
}回滚操作，开个记录修改的栈即可。
std::vector<std::pair<int*, int>> p;
auto record = [&](int &x) { p.push_back({&x, x}); };
std::reverse(p.begin(), p.end());
for (auto &[u, v] : p) *u = v;
p.clear();最后修改于 2021-08-13