緣起
掌握莫隊核心科技，來入坑一下二次離線莫隊~ 本文的例題是 洛谷 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)的，只是常數有點大——常數是
作死嘗試一把，體驗騙分的快感
//#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）式是以右端點右移動舉例的. 其中
即
但是因為題目強調自己不能和自己異或（例如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[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）時間得到各個貢獻的值, 而一共是
空間複雜度由於要存儲
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情況
顯然，我們最後的任務是優化空間複雜度.
其實上一版代碼耗費
第一類 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
參考[1]《優雅的暴力——莫隊算法》