P4462 [CQOI2018]异或序列莫队

题意：给定数列 \(a\) 和 \(k\) ,询问区间 \([l,r]\) 中有多少子区间满足异或和为 \(k\)。

莫队。我们可以记录前缀异或值 \(a_i\)，修改时，贡献为 \(c[a_i\bigoplus k]\) 。

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cmath>

#include<cstring>

#define R register int

using namespace std;

namespace Luitaryi {

inline int g() { R x=0,f=1;

	register char s; while(!isdigit(s=getchar())) f=s=='-'?-1:f;

	do x=x*10+(s^48); while(isdigit(s=getchar())); return x*f;

} const int N=100010;

int n,m,k,B,anss,a[N],c[N<<1],ans[N];

struct node { int l,r,id,pos;

	inline bool operator < (const node& that) const

		{return pos==that.pos?pos&1?r<that.r:r>that.r:pos<that.pos;}

}q[N];

inline void add(int x) {anss+=c[x^k],++c[x];}

inline void sub(int x) {--c[x],anss-=c[x^k];}

inline void main() {

	n=g(),m=g(),k=g(); B=sqrt(n+1);

	for(R i=1;i<=n;++i) a[i]=g()^a[i-1];

	for(R i=1;i<=m;++i)

		q[i].l=g()-1,q[i].r=g(),q[i].id=i,q[i].pos=q[i].l/B+1;

	sort(q+1,q+m+1);

	for(R i=1,l=1,r=0,LL,RR,id;i<=m;++i) {

		LL=q[i].l,RR=q[i].r,id=q[i].id;

		while(l<LL) sub(a[l++]); while(l>LL) add(a[--l]);

		while(r<RR) add(a[++r]); while(r>RR) sub(a[r--]); ans[id]=anss;

	} for(R i=1;i<=m;++i) printf("%d\n",ans[i]);

}

} signed main() {Luitaryi::main(); return 0;}

2019.11.25

巴特西

P4462 [CQOI2018]异或序列莫队

最新文章

热门文章

巴特西

P4462 [CQOI2018]异或序列 莫队

最新文章

热门文章

P4462 [CQOI2018]异或序列莫队