考虑莫队二次离线。剩下是平衡插入和查询复杂度的问题。
考虑现在的问题：要求 \(O(\sqrt{n})\) 往集合里插入一个数，\(O(1)\) 回答集合内有多少个数 \(x\) 满足 \(z \oplus x \le m\)（\(z\) 给定）。
考虑高低位分块。先钦定 \(z\) 在前 \(9\) 位时 \(z \oplus x < m\)，枚举 \(z\) 的前 \(9\) 位更新答案；然后钦定 \(z\) 前 \(9\) 位 \(= m \oplus x\)，枚举 \(z\) 的后 \(9\) 位更新答案。查询是 \(O(1)\) 的。
总时间复杂度 \(O(n + (\sqrt{n} + \sqrt{q}))\)。
code
// Problem: P7906 [Ynoi2005] rpxleqxq
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P7906
// Memory Limit: 128 MB
// Time Limit: 1500 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 200100;
const int maxm = 1000100;
int n, m, q, a[maxn], blo, bel[maxn];
ll ans[maxm], b[maxn];
struct node {
int l, r, i;
ll ans;
} qq[maxm];
namespace DS {
int f[555], g[555][555];
inline void init() {
mems(f, 0);
mems(g, 0);
}
inline void insert(int x) {
for (int i = 0; i < 512; ++i) {
f[i] += (((x >> 9) ^ i) < (m >> 9));
}
int t = (x ^ m) >> 9;
for (int i = 0; i < 512; ++i) {
g[t][i] += (((x & 511) ^ i) <= (m & 511));
}
}
inline int query(int x) {
return f[x >> 9] + g[(x >> 9) & 511][x & 511];
}
}
struct line {
int l, r, i, o;
line(int a = 0, int b = 0, int c = 0, int d = 0) : l(a), r(b), i(c), o(d) {}
};
vector<line> vc[maxn];
void solve() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
}
scanf("%d", &q);
for (int i = 1; i <= q; ++i) {
scanf("%d%d", &qq[i].l, &qq[i].r);
qq[i].i = i;
}
blo = ceil(n / sqrt(q));
for (int i = 1; i <= n; ++i) {
bel[i] = (i - 1) / blo + 1;
}
sort(qq + 1, qq + q + 1, [&](const node &a, const node &b) {
if (bel[a.l] != bel[b.l]) {
return bel[a.l] < bel[b.l];
} else if (bel[a.l] & 1) {
return a.r < b.r;
} else {
return a.r > b.r;
}
});
for (int i = 1; i <= n; ++i) {
b[i] = b[i - 1] + DS::query(a[i]);
DS::insert(a[i]);
}
int l = 1, r = 0;
for (int i = 1; i <= q; ++i) {
int L = qq[i].l, R = qq[i].r;
if (l > L) {
qq[i].ans -= b[l - 1] - b[L - 1] + l - L;
vc[r].pb(L, l - 1, i, 1);
l = L;
}
if (r < R) {
qq[i].ans += b[R] - b[r];
vc[l - 1].pb(r + 1, R, i, -1);
r = R;
}
if (l < L) {
qq[i].ans += b[L - 1] - b[l - 1] + L - l;
vc[r].pb(l, L - 1, i, -1);
l = L;
}
if (r > R) {
qq[i].ans -= b[r] - b[R];
vc[l - 1].pb(R + 1, r, i, 1);
r = R;
}
}
DS::init();
for (int i = 1; i <= n; ++i) {
DS::insert(a[i]);
for (line u : vc[i]) {
for (int j = u.l; j <= u.r; ++j) {
qq[u.i].ans += u.o * DS::query(a[j]);
}
}
}
for (int i = 1; i <= q; ++i) {
qq[i].ans += qq[i - 1].ans;
ans[qq[i].i] = qq[i].ans;
}
for (int i = 1; i <= q; ++i) {
printf("%lld\n", ans[i]);
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}