[CQOI2018]異或序列

\(\text{Problem}\)

經典的區間詢問異或和等于 \(k\) 的問題

\(1 \le n \le 10^5\)

\(\text{Solution}\)

考慮字首異或和，那麼統計變成 \(i, j \in[l-1,r](0\le i\le j\le n),s[i]\oplus s[j] = k\) 的數目

莫隊即可

\(\text{Code}\)

#include <cstdio>
#include <cmath>
#include <algorithm>
#define IN inline
#define RE register
using namespace std;

const int N = 1e5 + 5;
int n, m, k, a[N], ans[N], bl, buc[N], res;
struct node{int l, r, id;}Q[N];
IN bool cmp(node a, node b){return ((a.l / bl) ^ (b.l / bl)) ? (a.l < b.l) : (((a.l / bl) & 1) ? a.r > b.r : a.r < b.r);}
IN void add(int x){if (x == -1) return; res += buc[a[x] ^ k], ++buc[a[x]];}
IN void del(int x){if (x == -1) return; --buc[a[x]], res -= buc[a[x] ^ k];}

int main()
{
	scanf("%d%d%d", &n, &m, &k);
	for(RE int i = 1; i <= n; i++) scanf("%d", &a[i]), a[i] ^= a[i - 1];
	for(RE int i = 1; i <= m; i++) scanf("%d%d", &Q[i].l, &Q[i].r), --Q[i].l, Q[i].id = i;
	bl = n / sqrt(m / 2 * 3), sort(Q + 1, Q + m + 1, cmp); int l = -1, r = -1;
	for(RE int i = 1; i <= m; i++)
	{
		while (l > Q[i].l) add(--l);
		while (l < Q[i].l) del(l++);
		while (r < Q[i].r) add(++r);
		while (r > Q[i].r) del(r--);
		ans[Q[i].id] = res;
	}
	for(RE int i = 1; i <= m; i++) printf("%d\n", ans[i]);
}