[CQOI2018]异或序列
题目描述
已知一个长度为n的整数数列\(a_1,a_2,...,a_n\),给定查询参数l、r,问在\(a_l,a_{l+1},...,a_r\)区间内，有多少子序列满足异或和等于k。也就是说，对于所有的x,y (I ≤ x ≤ y ≤ r),能够满足\(a_x \bigoplus a_{x+1} \bigoplus ... \bigoplus a_y = k\)的x,y有多少组。
对于30%的数据，\(1 ≤ n, m ≤ 1000\)
对于100%的数据，\(1 ≤ n, m ≤ 10^5, 0 ≤ k, a_i ≤ 10^5,1 ≤ l_j ≤ r_j ≤ n\)
分析
\(\text{异或是一个神奇的运算符号！}\)
$\text{由}\ a \ xor \ b= c\ \text{ 可得 } \ \ c \ xor \ b= a\ \text{ 和 }\ c \ xor \ a= b\ $
\(\text{且 } a\ xor \ a =0 \ ,a\ xor\ 0=a\)
\(\text{我们设 }sum_i=\left[1,i\right]\text{ 的异或和}\)
$\text{所以一个区间 }\left[l,r\right]\text{ 的异或和为 }k $
\(\text{那么 }sum_{r}\ xor\ sum_{l-1}= k\ \ ,\ \ \ sum_r \ xor\ k=sum_{l-1}\)
\(\text{再加上}\)我们都学过的\(\text{莫队就轻松解决了}\)
Code：
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define Ld long double
const int N=2e6;
LL n,m,a[N],sq,l=1,r=0,now,ans[N],xo[N],la,k,cnt[N];//cnt为此时区间内以i为异或值的区间数
struct node{
LL l,r,id,bel;
}t[N];
inline LL read(){
LL s=0,w=1;char ch;
ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-'){w=-1;}ch=getchar();}
while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+ch-'0';ch=getchar();}
return s*w;
}
void print(LL x){
char F[200];LL cnt=0;
if(x<0) {x=-x;putchar('-');}
if(x==0){putchar('0');putchar('\n');return ;}
while(x){F[++cnt]=x%10;x/=10;}
while(cnt){putchar(F[cnt--]+'0');}
putchar('\n');
return ;
}
bool cmp(node a, node b){
return (a.bel^b.bel)?a.bel<b.bel:((a.bel&1)?a.r<b.r:a.r>b.r);
}
void del(LL pos){
--cnt[xo[pos]];//因为这个点要删了，所以区间内以此异或值结尾的区间数减1
now-=cnt[xo[pos]^k];
return ;
}
/*关于为什么del要先减再算答案
因为当k=0时，他自己也算进去了所以要先减
add同理
*/
void add(LL pos){
now+=cnt[xo[pos]^k];
cnt[xo[pos]]++;
return ;
}
int main(){
n=read(),m=read(),k=read();
sq=sqrt(n);
for(int i=1;i<=n;i++){
xo[i]=read();
xo[i]=xo[i-1]^xo[i];
}
for(int i=1;i<=m;i++){
t[i].l=read()-1;
t[i].r=read();
t[i].id=i;
t[i].bel=(t[i].l-1)/sq+1;
}
sort(t+1,t+1+m,cmp);
for(int i=1;i<=m;i++){
LL lt=t[i].l,rt=t[i].r;
while(l<lt) del(l++);
while(l>lt) add(--l);
while(r<rt) add(++r);
while(r>rt) del(r--);
ans[t[i].id]=now;
}
for(int i=1;i<=m;i++){
print(ans[i]);
}
return 0;
}