【luogu P4887】【模板】莫队二次离线（第十四分块(前体)）（莫队）

【模板】莫队二次离线（第十四分块(前体)）

题目链接：luogu P4887

题目大意

给你一个序列，每次查询一个区间 l~r，有多少个二元组 (i,j) 满足 l<=i异或和在二进制下恰好 k 位，k 是固定的。

思路

因为这个恰好 k 位，导致似乎不太可能用什么数据结构维护，而且也没有修改。
发现可以离线，试着莫队。

那发现每次移动，会加上或者减去的是一个点跟一个区间之间匹配的贡献。
而且一定是 $x,(x+1,y)$ 或者 $(x,y-1),y$ 这种相邻的。
那你考虑怎么统计，那区间我们可以先拆一个前缀和。

先看 $x,(x+1,y)$。
那就是 $x,(1,y)$ 的减去 $x,(1,x)$ 的。
发现一个特点，就是你这个样子的贡献只会出现在移动左端点的时候。
那这个时候，$y$ 是固定的，那你 $x,(1,y)$ 在一整次运动中 $y$ 都是一样的，那我们可以记录下每个 $y$ 有哪些 $x$ 要回答，然后再离线出来，扫过去维护。
那怎么维护呢？

那你 $y$ 从小到大，每次多一个数，你就预处理出所有二进制下 $1$ 的个数为 $k$ 的数 $o_i$，然后一个桶 $p_i$ 表示问的那个单点的答案，那你每次多一个 $x$，你就把 $p_{x\oplus o_i}$ 加一即可。
那再看另一个，会发现是 $x,(1,x)$ 这样的形式，那这种只会有 $O(n)$ 个，那我们直接预处理出所有的结果就行，也是用上面的方式求。

那对于 $(x,y-1),y$，不难知道你就是从后往前来处理，拆成 $(x,n),y$ 减去 $(y,n),y$ 这样，然后也是同样的方法再做一次就可以了。
（不过好像说可以也拆成跟上面一样从前往后的然后再弄）

代码

#include
#include
#include
#include
#define ll long long

using namespace std;

const int N = 1e5 + 100;
const int M = 16384;
int n, m, k, a[N], count_[M], fine[M], cnt, B, tot, tot_, an;
int left[N], right[N], tong[M], bl[N], br[N], blo[N];
struct node {
	int l, r, id;
}q[N];
struct node_ {
	int id, ask_p, gl, gr;
}qs[N], qt[N];
ll ans[N], vals[N], valr[N];

bool cmp(node x, node y) {
	if (blo[x.l] != blo[y.l]) return blo[x.l] < blo[y.l];
	return x.r < y.r;
}

bool cmp1(node_ x, node_ y) {
	return x.ask_p < y.ask_p;
}
bool cmp2(node_ x, node_ y) {
	return x.ask_p > y.ask_p;
}

int main() {
//	freopen("read.txt", "r", stdin);
//	freopen("write.txt", "w", stdout);
	
	scanf("%d %d %d", &n, &m, &k); B = sqrt(m);
	for (int i = 1; i < M; i++) count_[i] = count_[i ^ (i & (-i))] + 1;
	for (int i = 0; i < M; i++) if (count_[i] == k) fine[cnt++] = i;
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	
	for (int i = 1; i <= n; i++) {
		left[i] = tong[a[i]];
		for (int j = 0; j < cnt; j++) tong[a[i] ^ fine[j]]++;
	}
	memset(tong, 0, sizeof(tong));
	for (int i = n; i >= 1; i--) {
		right[i] = tong[a[i]];
		for (int j = 0; j < cnt; j++) tong[a[i] ^ fine[j]]++;
	}
	memset(tong, 0, sizeof(tong));
	
	for (int i = 1; i <= n; i++) {
		blo[i] = (i - 1) / B + 1;
		if (!bl[blo[i]]) bl[blo[i]] = i;
		br[blo[i]] = i;
	}
	for (int i = 1; i <= m; i++) scanf("%d %d", &q[i].l, &q[i].r), q[i].id = i;
	sort(q + 1, q + m + 1, cmp);
	int x = 1, y = 0;
	for (int i = 1; i <= m; i++) {
		if (y < q[i].r) {
			tot++; qs[tot].id = tot; qs[tot].ask_p = x - 1; qs[tot].gl = y + 1; qs[tot].gr = q[i].r;
			y = q[i].r;
		}
		if (y > q[i].r) {
			tot++; qs[tot].id = tot; qs[tot].ask_p = x - 1; qs[tot].gl = q[i].r + 1; qs[tot].gr = y;
			y = q[i].r;
		}
		if (x > q[i].l) {
			tot_++; qt[tot_].id = tot_; qt[tot_].ask_p = y + 1; qt[tot_].gl = q[i].l; qt[tot_].gr = x - 1;
			x = q[i].l;
		}
		if (x < q[i].l) {
			tot_++; qt[tot_].id = tot_; qt[tot_].ask_p = y + 1; qt[tot_].gl = x; qt[tot_].gr = q[i].l - 1;
			x = q[i].l;
		}
	}
	
	sort(qs + 1, qs + tot + 1, cmp1);
	memset(tong, 0, sizeof(tong));
	for (int i = 0, j = 1; i <= n; i++) {
		if (i) {for (int j = 0; j < cnt; j++) tong[a[i] ^ fine[j]]++;}
		while (j <= tot && qs[j].ask_p == i) {
			for (int p = qs[j].gl; p <= qs[j].gr; p++) vals[qs[j].id] += tong[a[p]];
			j++;
		}
	}
	sort(qt + 1, qt + tot_ + 1, cmp2);
	memset(tong, 0, sizeof(tong));
	for (int i = n + 1, j = 1; i >= 1; i--) {
		if (i != n + 1) {for (int j = 0; j < cnt; j++) tong[a[i] ^ fine[j]]++;}
		while (j <= tot_ && qt[j].ask_p == i) {
			for (int p = qt[j].gl; p <= qt[j].gr; p++) valr[qt[j].id] += tong[a[p]];
			j++; 
		}
	}
	
	x = 1; y = 0; int nowl = 0, nowr = 0; ll an = 0;
	for (int i = 1; i <= m; i++) {
		if (y < q[i].r) {
			for (int j = y + 1; j <= q[i].r; j++) an += left[j];
			an -= vals[++nowl];
			y = q[i].r;
		}
		if (y > q[i].r) {
			for (int j = q[i].r + 1; j <= y; j++) an -= left[j];
			an += vals[++nowl];
			y = q[i].r;
		}
		if (x > q[i].l) {
			for (int j = q[i].l; j < x; j++) an += right[j]; 
			an -= valr[++nowr];
			x = q[i].l;
		}
		if (x < q[i].l) {
			for (int j = x; j < q[i].l; j++) an -= right[j];
			an += valr[++nowr];
			x = q[i].l;
		}
		ans[q[i].id] = an; 
	}
	for (int i = 1; i <= m; i++) printf("%lld\n", ans[i]);
	
	return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126