莫队新科技——二次离线莫队入门
缘起
掌握莫队核心科技，来入坑一下二次离线莫队~ 本文的例题是 洛谷 P4887 模板 莫队二次离线（第十四分块(前体)）
分析
珂朵莉给了你一个序列a，每次查询给一个区间 [l,r]
查询 l<=i<j<=r, 且ai xor aj 的二进制表示下有k个比特位1的二元组 (i,j) 的个数
输入
第一行三个数表示n,m,k
第二行n个数表示序列a
之后m行，每行两个数l,r表示一次查询
输出
输出m行，每行一个数表示查询的结果
输入样例
5 5 2
3 4 8 0 2
4 5
3 5
1 4
2 5
1 5
输出样例
0
1
2
3
4
1≤n,m≤1e5,0≤ai,k<16384首先，二次离线莫队的前置技能是 【1】《优雅的暴力——莫队算法》
二次离线莫队是一个新的科技，由 神仙 lxl 2018年 大力YY出的技巧，可以处理的问题一般长下面的样子
一个序列a，m次询问，每次询问a[l,...,r]中有多少对(x,y)(l<=x<y<=r)满足某条件而在这道题中，所谓的某条件也就是x xor y的二进制表示下有k个比特位1
其实更一般的, 二次离线莫队基于 莫队+扫描线 思想, 适用于满足以下条件的题目
- 可以用莫队切
- add/sub 的时间不是O(1)或者说即便是O(1)但是常数巨大, 更确切讲, 莫队四句中扩展或者删除一个点对答案的影响取决于当前区间的长度.
- 第2条中的一个点对答案的影响可用前缀写成差分的形式.
二次离线莫队依旧是莫队嘛，所以肯定先要按莫队的套路来，我们先不考虑什么二次离线莫队，先用不带修莫队来切.
为了方便讲解，我们设输入的那个序列为a[1]~a[n], 因为是不带修的莫队, 所以每次只需要考虑add、sub函数怎么写就行了.
add(i) 是加入一个点i 之后对res的影响, 而i假设当前区间是 [l, r], 则加入i = r + 1(即右端点右移动) 或者 加入i = r-1（即左端点左移动）, 则导致对res的影响是
所以我们要能快速求出上式右边集合的大小即可. 而这只需要考虑集合
即可, 然后(1)式的右边就等于
其中 num[i], 0<=i<16384 是 i 这个值出现的次数. 即
就是这次移动带来res的变动值（下文称这种变动值为a[i]对区间[l, r]的贡献）. 这是add的分析, sub是同理的.
下面考虑一下这种裸的不带修莫队的做法的复杂度. 显然，add、sub的复杂度依旧是O(1)的，只是常数有点大——常数是 , 也就是说, 裸的不带修做法的复杂度达到了 , 考虑到n达到了10w, 所以应该会被T掉的.
作死尝试一把，体验骗分的快感
//#include "stdafx.h"
//#define LOCAL
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <list>
using namespace std;
#define int long long
#define re register int
#define FE(cur) for(re h = head[cur], to; ~h; h = g[h].nxt)
#define ilv inline void
#define ili inline int
#define ilc inline char
#define SQUARE(x) ((x) * (x))
namespace fastio
{
const int BUF = 1 << 21;
char fr[BUF], fw[BUF], *pr1 = fr, *pr2 = fr;int pw;
ilc gc() { return pr1 == pr2 && (pr2 = (pr1 = fr) + fread(fr, 1, BUF, stdin), pr1 == pr2) ? EOF : *pr1++; }
ilv flush() { fwrite(fw, 1, pw, stdout); pw = 0; }
ilv pc(char c) { if (pw >= BUF) flush(); fw[pw++] = c; }
ilv read(int &x)
{
x = 0; int f = 1; char c = gc();
while(!isdigit(c)) { if (c == '-') f = -1; c = gc(); }
while(isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = gc();
x *= f;
}
ilv write(int x) { if (x < 0) pc('-'), x = -x; if (x > 9) write(x / 10); pc(x % 10 + 48); }
ilv writeln(int x) { write(x);pc(10); }
ilv read(char *x)
{
char c = gc();
while(!isalpha(c)) c = gc();
while (isalpha(c)) *x++ = c, c = gc();
*x = 0;
}
ilv write(char *x) { while(*x) pc(*x++); }
ilv writeln(char *x) { write(x); pc(10); }
} using namespace fastio;
const int maxn = 1e5+5, FULL = (1 << 14);
int n, m, k, a[maxn], bel[maxn], B, ans[maxn], l = 1, r, num[FULL], kbit[3500], tot, res;
struct Q
{
int l, r, id;
bool operator <(const Q &rhs) const
{
return bel[l] == bel[rhs.l] ? r < rhs.r : bel[l] < bel[rhs.l];
}
} qs[maxn];
ili popcnt(int i)
{
int ans = 0;
while(i)
{
ans += i & 1;
i >>= 1;
}
return ans;
}
ilv add(int i) // O(3432)的操作
{
for (re j = 1; j <= tot; j++)
{
res += num[a[i] ^ kbit[j]];
}
++num[a[i]];
}
ilv sub(int i)
{
--num[a[i]];
for (re j = 1; j <= tot; j++)
{
res -= num[a[i] ^ kbit[j]];
}
}
signed main()
{
#ifdef LOCAL
freopen("d:\\data.in", "r", stdin);
//freopen("d:\\my.out", "w", stdout);
#endif
read(n), read(m), read(k); B = sqrt(1.0 * n);
for (re i = 0; i < FULL; i++)
{
if (popcnt(i) == k)
{
kbit[++tot] = i;
}
}
for (re i = 1; i <= n; i++)
{
read(a[i]);
bel[i] = (i - 1) / B + 1;
}
for (re i = 1; i <= m; i++)
{
read(qs[i].l), read(qs[i].r), qs[i].id = i;
}
sort(qs + 1, qs + m + 1);
for (re i = 1; i <= m; i++)
{
while(qs[i].l < l)
{
add(--l);
}
while(qs[i].l > l)
{
sub(l++);
}
while(qs[i].r < r)
{
sub(r--);
}
while(qs[i].r > r)
{
add(++r);
}
ans[qs[i].id] = res;
}
for (re i = 1; i <= m; i++)
{
writeln(ans[i]);
}
flush();
return 0;
}ac情况（应该不会wa，仅仅是慢~）
所以我们应该怎么補完上面的算法呢? 或者说考虑一下上面的代码耗时在哪里? 其实我们考虑一下朴素莫队的移动过程, 注意，我们指的询问区间是按照52行规则排序之后的区间（下面不再重复声明这一点）. 而从前一个区间移动移动到后一个区间造成的res的变动值不就是左端点的移动和右端点的移动造成的吗?
将(1)式右侧用前缀写为差分形式（此处可以回忆一下我们说的二次离线莫队的适用范围）
上面的（3）式是以右端点右移动举例的. 其中 指的是 中和x异或之后恰好有k个比特位1的元素的个数. 类似的可以写出右端点左移动、左端点左移动、左端点右移动的（3）式.
即
但是因为题目强调自己不能和自己异或（例如k=0, 即含有0个比特位1，则自己和自己异或也是得到0），所以上面的式子变为
即我们从一个区间移动到另一个区间，其实四句while就在以在线的方式干下面的事情.
即一个数对一段区间的贡献.
那为什么我们不将对同一个前缀做的贡献开vector收集起来然后一口气计算这些贡献? 因为很有可能同一段前缀a[1,..,i]，我们要计算不同的数,例如x, y对该前缀的贡献，按照上面被T掉的做法，其实是x和y分别各自跑了一次O(3432)的程序, 而其实如果我们事先知道了要处理 x, y 对 前缀a[1,..,i]的贡献的话，我们大可以放在一起处理，这样就大大节省了时间. 因为我们假设已经知道了 前缀a[1,..,i]的分布状态（即当前前缀为a[1,..,i]的时候num数组的样子），那么我们完全可以再维护一个数组 t, 其中 t[z， 0<=z<16384]表示当前前缀a[1,..,i]中与z异或之后恰好有k个比特位1的元素的个数. 那么对于x,y对当前前缀a[1,..,i]的贡献不就恰好就是 t[x]、 t[y] 了么? 这样就能一口气处理而不必次次跑 add、sub这种自带3432超大常数的O(1)程序了. 注意，维护t[z]数组这种做法的思想其实就是扫描线的思想——不断的加入点（本题没有点离开，因为前缀是不断的扩展的），然后维护答案.
纵观这个处理方法，不就是将跑不带修莫队过程中会遇到的所有8种贡献再次离线出来吗? 因为这是再一次离线（莫队本身有一次离线），所以这个算法才叫做二次离线莫队.
于是我们将(4)、(5)、(6)、(7) 涉及到的8种需要处理的贡献离线出来.
- {a[l-1]，r， i}
- {a[l-1]，l-2， -i}
- {a[l]，r， -i}
- {a[l]，l-1， i}
- {a[r]，r-1， -i}
- {a[r]，l-1， i}
- {a[r+1]，r， i}
- {a[r+1]，l-1， -i}
其中 {a[x], j, i} 指的是 a[x] 对 前缀a[1,..,j]的贡献, 而且这种贡献是要加（i > 0）或者减（i < 0）在第 abs(i) 个询问上的。
具体离线方法就是模拟跑莫队，但是并不实质性的进行add/sub, 对每个前缀a[1,..,j] 开一个vector, 实质上做的事情是往这些vector中装二元组 {x, i}（表示a[x]对前缀a[1,..,j]的贡献要加（i>0）或者减（i<0）在第|i|个询问上）.
离线完毕，就要开始离线计算这些贡献的值，秉着离线的精神，我们对考察的当前前缀就要一口气计算出所有处在它开的vector中的二元组（即一个待计算的贡献）的答案. 然后加到相应的qs中去.
为了一口气计算能够快速, 期间维护一个数组 t, 然后按照 i从1到n考虑当前前缀a[1,..,i]（其实就是不断的往当前前缀中加入a[i], 1<=i<=n）, 然后t[z]就像上面说的那样，维护着当前前缀a[1,..,i]中和z异或之后恰好有k个1的数的个数. 在我们遍历考察当前前缀的时候, 顺带O(3432)维护一下t即可.
注意，此时我们计算出的只是从一个询问区间到另一个询问区间的变化值（即若干贡献的总和），这其实就是询问区间答案的差分数组, 所以最后还要做一次差分数组到原数组的还原操作（其实就是做一次前缀和）就得到答案了.
复杂度从之前的优化到了
其中 3432n 是维护t数组的复杂度, 这构成了第一部分的复杂度, 因为t数组的存在, 所以我们可以O(1)（常数是1）时间得到各个贡献的值, 而一共是 个贡献, 所以这构成了第二部分的复杂度, 所以总的复杂度是
空间复杂度由于要存储 次移动, 而每次移动其实要拆成两个前缀，所以常数还要乘以2, 所以空间复杂度是 的.
emmm... 应该可以过了~
于是，我天真的写了第二版的代码
//#include "stdafx.h"
//#define LOCAL
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <list>
using namespace std;
#define int long long
#define re register int
#define FE(cur) for(re h = head[cur], to; ~h; h = g[h].nxt)
#define ilv inline void
#define ili inline int
#define ilc inline char
#define SQUARE(x) ((x) * (x))
typedef pair<int, int> P;
namespace fastio
{
const int BUF = 1 << 21;
char fr[BUF], fw[BUF], *pr1 = fr, *pr2 = fr;int pw;
ilc gc() { return pr1 == pr2 && (pr2 = (pr1 = fr) + fread(fr, 1, BUF, stdin), pr1 == pr2) ? EOF : *pr1++; }
ilv flush() { fwrite(fw, 1, pw, stdout); pw = 0; }
ilv pc(char c) { if (pw >= BUF) flush(); fw[pw++] = c; }
ilv read(int &x)
{
x = 0; int f = 1; char c = gc();
while(!isdigit(c)) { if (c == '-') f = -1; c = gc(); }
while(isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = gc();
x *= f;
}
ilv write(int x) { if (x < 0) pc('-'), x = -x; if (x > 9) write(x / 10); pc(x % 10 + 48); }
ilv writeln(int x) { write(x);pc(10); }
ilv read(char *x)
{
char c = gc();
while(!isalpha(c)) c = gc();
while (isalpha(c)) *x++ = c, c = gc();
*x = 0;
}
ilv write(char *x) { while(*x) pc(*x++); }
ilv writeln(char *x) { write(x); pc(10); }
} using namespace fastio;
const int maxn = 1e5+5, FULL = 1 << 14;
int n, m, k, ans[maxn], B, bel[maxn], a[maxn], l = 1, r, kbit[3500], tot, t[FULL]; // t[z] 是当前前缀中和z异或恰好有k个比特位1的元素的个数
struct Q
{
int l, r, id, ans;
bool operator <(const Q &rhs) const
{
return bel[l] == bel[rhs.l] ? r < rhs.r : bel[l] < bel[rhs.l];
}
} qs[maxn];
vector<P> ts[maxn];
ili popcnt(int i)
{
int ans = 0;
while(i)
{
ans += i & 1;
i >>= 1;
}
return ans;
}
ilv init()
{
for (re i = 0; i < FULL; i++)
{
if (popcnt(i) == k)
{
kbit[++tot] = i;
}
}
}
ilv kk(int x)
{
for (re i = 1; i <= tot; i++)
{
++t[x ^ kbit[i]];
}
}
signed main()
{
#ifdef LOCAL
freopen("d:\\data.in", "r", stdin);
//freopen("d:\\my.out", "w", stdout);
#endif
read(n), read(m), read(k); B = sqrt(1.0 * n);
init();
for (re i = 1; i <= n; i++)
{
read(a[i]), bel[i] = (i - 1) / B + 1;
}
for (re i = 1; i <= m; i++)
{
read(qs[i].l), read(qs[i].r), qs[i].id = i;
}
sort(qs + 1, qs + m + 1);
for (re i = 1; i <= m; i++) // 模拟跑莫队, 离线所有贡献
{
while(qs[i].l < l)
{
if (r > 0)
{
ts[r].push_back(P(l - 1, i));
}
if (l > 2)
{
ts[l - 2].push_back(P(l - 1, -i));
}
--l;
}
while(qs[i].l > l)
{
if (r > 0)
{
ts[r].push_back(P(l, -i));
}
if (l > 1)
{
ts[l - 1].push_back(P(l, i));
}
++l;
}
while(qs[i].r < r)
{
if (r > 1)
{
ts[r - 1].push_back(P(r, -i));
}
if (l > 1)
{
ts[l - 1].push_back(P(r, i));
}
--r;
}
while(qs[i].r > r)
{
if (r > 0)
{
ts[r].push_back(P(r + 1, i));
}
if (l > 1)
{
ts[l - 1].push_back(P(r + 1, -i));
}
++r;
}
}
for (re i = 1; i <= n; i++)
{
kk(a[i]); // O(3432) 维护t
for (re j = 0, len = ts[i].size(), x, y, gx; j < len; j++) // O(sqrt{n})计算贡献
{
x = ts[i][j].first, y = ts[i][j].second; // 第|y|个询问, a[x]对当前前缀的贡献
gx = t[a[x]]; // a[x]对第|y|个询问作用在当前前缀上的贡献值
if (!k && x <= i) // 如果题目中k=0, 且x <= i, 则因为一个数和自己异或得到的也是0, 但是题目要求不能将自己和自己的异或计入答案, 所以要去掉这种情况(因为x<=i, 所以x被计入答案了)
{
--gx;
}
if (y < 0)
{
qs[-y].ans -= gx;
}
else
{
qs[y].ans += gx;
}
}
} // 离线计算所有贡献
for (re i = 1; i <= m; i++) // 差分还原
{
qs[i].ans += qs[i - 1].ans;
}
for (re i = 1; i <= m; i++)
{
ans[qs[i].id] = qs[i].ans;
}
for (re i = 1; i <= m; i++)
{
writeln(ans[i]);
}
flush();
return 0;
}ac情况
显然，我们最后的任务是优化空间复杂度.
其实上一版代码耗费 是毒瘤. 其实仔细想一下，不就是存储这些离线的贡献么? 而仔细观察一下(4)，(5),(5),(7) 这些贡献，其实就分为2类
- 第一类 a[x+1] 对 前缀a[1,..,x]的贡献,其中 x 会变化
- 第二类 a[l,..,r] 中所有数对 前缀a[1,..,x] 的贡献, 其中在一次端点的移动中,x是不会变化的.
要注意这个不会变化, 所以我们完全可以将上面两类贡献分开来计算. 其中第二类贡献可以记做 (l, r, x, i或者-i), 也就是只需要标记端点移动的起止即可，而上一份代码我们是怎么存的?
(l, x, i或者-i);
(l + 1, x, i或者-i);
...
...
(r - 1, x, i或者-i);
(r, x, i或者-i);耗费了 O(r - l) 的空间存储了这些离线的贡献！！！即原本只需要一个 (l, r, x, i 或者-i) 就能记录的离线贡献竟然花费了O(r - l) 的空间存储, 那不MLE才怪呢!!!
所以我们就知道该如何改进上面的代码了，而且空间复杂度被优化为O(m)的了, 这就完全可以接受了
最后一击~ (ง •̀_•́)ง
//#include "stdafx.h"
//#define LOCAL
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <list>
using namespace std;
#define int long long
#define re register int
#define FE(cur) for(re h = head[cur], to; ~h; h = g[h].nxt)
#define ilv inline void
#define ili inline int
#define ilc inline char
#define SQUARE(x) ((x) * (x))
typedef pair<int, int> P;
namespace fastio
{
const int BUF = 1 << 21;
char fr[BUF], fw[BUF], *pr1 = fr, *pr2 = fr;int pw;
ilc gc() { return pr1 == pr2 && (pr2 = (pr1 = fr) + fread(fr, 1, BUF, stdin), pr1 == pr2) ? EOF : *pr1++; }
ilv flush() { fwrite(fw, 1, pw, stdout); pw = 0; }
ilv pc(char c) { if (pw >= BUF) flush(); fw[pw++] = c; }
ilv read(int &x)
{
x = 0; int f = 1; char c = gc();
while(!isdigit(c)) { if (c == '-') f = -1; c = gc(); }
while(isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = gc();
x *= f;
}
ilv write(int x) { if (x < 0) pc('-'), x = -x; if (x > 9) write(x / 10); pc(x % 10 + 48); }
ilv writeln(int x) { write(x);pc(10); }
ilv read(char *x)
{
char c = gc();
while(!isalpha(c)) c = gc();
while (isalpha(c)) *x++ = c, c = gc();
*x = 0;
}
ilv write(char *x) { while(*x) pc(*x++); }
ilv writeln(char *x) { write(x); pc(10); }
} using namespace fastio;
const int maxn = 1e5+5, FULL = 1 << 14;
int n, m, k, ans[maxn], B, bel[maxn], a[maxn], l = 1, r, kbit[3500], tot, t[FULL], pref[maxn]; // pref[i] 是 a[i] 对前缀a[1,..,i-1] 的贡献
struct Q
{
int l, r, id, ans;
bool operator <(const Q &rhs) const
{
return bel[l] == bel[rhs.l] ? r < rhs.r : bel[l] < bel[rhs.l];
}
} qs[maxn];
struct T
{
int l, r, i; // 意义是a[l,...,r] 对 某前缀(到底是哪个前缀要看它在哪个vector中)做贡献, 而且这部分贡献是要加在(i>0)(或减去i<0)贡献 |i| 上的.
T(int l, int r, int i):l(l), r(r), i(i){}
};
vector<T> ts[maxn];
ili popcnt(int i)
{
int ans = 0;
while(i)
{
ans += i & 1;
i >>= 1;
}
return ans;
}
ilv init()
{
for (re i = 0; i < FULL; i++)
{
if (popcnt(i) == k)
{
kbit[++tot] = i;
}
}
}
ilv kk(int x)
{
for (re i = 1; i <= tot; i++)
{
++t[x ^ kbit[i]];
}
}
signed main()
{
#ifdef LOCAL
freopen("d:\\data.in", "r", stdin);
//freopen("d:\\my.out", "w", stdout);
#endif
read(n), read(m), read(k); B = sqrt(1.0 * n);
init();
for (re i = 1; i <= n; i++)
{
read(a[i]), bel[i] = (i - 1) / B + 1;
}
for (re i = 1; i <= m; i++)
{
read(qs[i].l), read(qs[i].r), qs[i].id = i;
}
sort(qs + 1, qs + m + 1);
for (re i = 1; i < n; i++)
{
kk(a[i]);
pref[i + 1] = t[a[i + 1]];
}
for (re i = 1; i <= m; i++) // 累加第一类贡献并离线第二类贡献
{
// 左端点左移
if (qs[i].l < l) // 打标记第二类贡献(即离线第二类贡献)
{
if (r > 0)
{
ts[r].push_back(T(qs[i].l, l - 1, i));
}
for (re j = l - 1; j >= qs[i].l; j--) // 累加第一类贡献
{
qs[i].ans -= pref[j];
}
l = qs[i].l;
}
// 左端点右移
if (qs[i].l > l)
{
if (r > 0)
{
ts[r].push_back(T(l, qs[i].l - 1, -i));
}
for (re j = l; j <= qs[i].l - 1; j++)
{
qs[i].ans += pref[j];
}
l = qs[i].l;
}
// 右端点左移
if (qs[i].r < r)
{
if (l > 1)
{
ts[l - 1].push_back(T(qs[i].r + 1, r, i));
}
for (re j = r; j >= qs[i].r + 1; j--)
{
qs[i].ans -= pref[j];
}
r = qs[i].r;
}
// 右端点右移
if (qs[i].r > r)
{
if (l > 1)
{
ts[l - 1].push_back(T(r + 1, qs[i].r, -i));
}
for (re j = r + 1; j <= qs[i].r; j++)
{
qs[i].ans += pref[j];
}
r = qs[i].r;
}
}
memset(t, 0, sizeof(t)); // 因为要重新走一遍前缀
for (re i = 1; i <= n; i++)
{
kk(a[i]);
for (re j = 0, len = ts[i].size(), x, y, z, gx; j < len; j++)
{
x = ts[i][j].l, y = ts[i][j].r, z = ts[i][j].i; // a[x, y] 对 第|z| 个询问的第二类贡献(z >0 则就是加, z <0 就是减)
for (re p = x; p <= y; p++)
{
gx = t[a[p]];
if (!k && p <= i)
{
--gx;
}
if (z < 0)
{
qs[-z].ans -= gx;
}
else
{
qs[z].ans += gx;
}
}
}
}
for (re i = 1; i <= m; i++)
{
qs[i].ans += qs[i - 1].ans;
}
for (re i = 1; i <= m; i++)
{
ans[qs[i].id] = qs[i].ans;
}
for (re i = 1; i <= m; i++)
{
writeln(ans[i]);
}
flush();
return 0;
}ac情况
所属题目
P4887 【模板】莫队二次离线（第十四分块(前体)）
评测状态
Accepted
评测分数
100
编程语言
C++
代码长度
4.24KB
用时
949ms
内存
19.34MB参考
腾讯云开发者
