脚本宝典收集整理的这篇文章主要介绍了[CQOI2018]异或序列，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

(text{Problem})

经典的区间询问异或和等于 (k) 的问题 (1 le n le 10^5)

(text{Solution})

考虑前缀异或和，那么统计变成 (i, j in[l-1,r](0le ile jle 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("%dn", ans[i]);
}

脚本宝典总结

以上是脚本宝典为你收集整理的[CQOI2018]异或序列全部内容，希望文章能够帮你解决[CQOI2018]异或序列所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。