bzoj 5301: [Cqoi2018]异或序列 (莫队算法)

链接:https://www.lydsy.com/JudgeOnline/problem.php?id=5301

题面;

5301: [Cqoi2018]异或序列

Time Limit: 10 Sec  Memory Limit: 512 MB
Submit: 476  Solved: 358
[Submit][Status][Discuss]

Description

已知一个长度为 n 的整数数列 a[1],a[2],…,a[n] ,给定查询参数 l、r ,问在 [l,r] 区间内,有多少连续子
序列满足异或和等于 k 。
也就是说,对于所有的 x,y (l≤x≤y≤r),能够满足a[x]^a[x+1]^…^a[y]=k的x,y有多少组。
 

Input

输入文件第一行,为3个整数n,m,k。
第二行为空格分开的n个整数,即ai,a2,….an。
接下来m行,每行两个整数lj,rj,表示一次查询。
1≤n,m≤105,O≤k,ai≤105,1≤lj≤rj≤n

Output

输出文件共m行,对应每个查询的计算结果。

Sample Input

4 5 1
1 2 3 1
1 4
1 3
2 3
2 4
4 4

Sample Output

4
2
1
2
1
 
思路:
因为区间[a,b]异或和可以由区间[1,a-1]和[1,b]异或得到,我们可以先预处理出前缀和,扔到莫队里维护,因为 a^b=k.那么 b = k^a,那么对a[i]来说,能与其异或成k的数就是 k^a[i],加上这个数的数量,在莫队里维护下每个值的数量就好了
 
因为这里存的是前缀和,所以存询问的时候应该是 [l-1,r].
实现代码;
#include<bits/stdc++.h>
using namespace std;
const int M = 1e5+;
int num[M],a[M],blo,k,ans,b[M];
struct node{
int l,r,id;
bool operator < (const node &cmp)const {
if(l/blo == cmp.l/blo) return r < cmp.r;
return l/blo < cmp.l/blo;
}
}q[M]; void add(int x){
ans += num[k^a[x]];
num[a[x]]++;
} void del(int x){
ans -= num[k^a[x]];
num[a[x]]--;
} int main()
{
int n,m;
cin>>n>>m>>k;
blo = sqrt(n);
for(int i = ;i <= n;i ++){
cin>>a[i];
a[i] = a[i]^a[i-];
}
for(int i = ;i <= m;i ++){
cin>>q[i].l>>q[i].r;
q[i].l --;
q[i].id = i;
}
sort(q+,q+m+);
int l = ,r = ;
ans = ;
for(int i = ;i <= m;i ++){
while(l < q[i].l) del(l),l++;
while(l > q[i].l) l--,add(l);
while(r < q[i].r) r++,add(r);
while(r > q[i].r) del(r),r--;
b[q[i].id] = ans;
}
for(int i = ;i <= m;i ++){
cout<<b[i]<<endl;
} }
 
上一篇:F1赛道 - Bahrain International Circuit | 巴林国际赛道


下一篇:面向对象的 CSS (OOCSS)