Time Limit: 2000 ms Memory Limit: 256 MB
Description
给定一个含有n个整数的序列 a1, a2,..., an.
定义 f(x,x) = a[x], f(x,y) = a[x] xor a[x + 1] xor ... xor a[y] (y > x).
本题设有m组询问,每组询问含有两个参数 (l, r) 。对于每组询问,你需要回答有多少个二元组 (x, y) 满足 l <= x <= y <= r 并且 f(x, y) = k.
Input
第一行有3个整数, n, m, k(1 <= n <= 100000, 1 <= m <= 100000, 0 <= k < 10^6).
第二行共有 n 个非负整数代表整个序列,每个整数均不超过 10^6.
接下来m行,每行两个整数 (li, ri), li <= ri
Output
对于每组询问,输出一行表示有多少满足上述条件的二元组。
Sample Input |
Sample Output |
5 2 1 |
2 4 |
Hint
对于10%的数据,$n, m leq 500$
对于30%的数据,$n, m leq 3000$
对于50%的数据,$n, m leq 30000$
对于100%的数据,$n, m leq 100000$
题解:
一看范围就知道是标准$nsqrt{n}$莫队啊,是我今天感冒脑抽了想不出这么简单的处理吗......
$[l,r]$异或起来的值刚好等于$k$,维护异或前缀和$a$后,等价于判断$a_{l-1}hat{} a_{r}$是否等于$k$。
那么用莫队在这个异或前缀和数组上爬。
维护莫队中统计每种值出现次数的数组$cnt$,$cnt_i$表示值为$i$的有多少。
这样一来,加入一位$x$对莫队的影响就是$ans+=cnt_{a[x]hat{} k}$,删去一位对莫队的影响就是$ans-=cnt_{a[x]hat{} k}$
当然还要维护$cnt$,加入时先统计影响,再将$cnt_{a[x]}++$;删除时先从$cnt$里抹掉:$cnt_{a[x]}--$,再统计影响。
Tips:
1.原本$[l,r]$的询问,转换后最大要考虑到$[l-1,r]$,所以把询问的左端点都-1.
2.异或后值可能大于1000000,需多开一倍。
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include <cstdio> 2 #include <cmath> 3 #include <algorithm> 4 using namespace std; 5 typedef long long ll; 6 const int N=100010; 7 int n,m,k,di,a[N],cnt[2000010]; 8 ll now,out[N]; 9 struct Query{ 10 int l,r,id; 11 friend bool operator < (Query x,Query y){ 12 x.l++; y.l++; 13 if(x.l/di!=y.l/di) return x.l/di<y.l/di; 14 return x.r<y.r; 15 } 16 }q[N]; 17 void add(int x){ 18 now+=cnt[a[x]^k]; 19 cnt[a[x]]++; 20 } 21 void dec(int x){ 22 cnt[a[x]]--; 23 now-=cnt[a[x]^k]; 24 } 25 int main(){ 26 scanf("%d%d%d",&n,&m,&k); 27 di=(int)sqrt(n); 28 for(int i=1,x;i<=n;i++){ 29 scanf("%d",&x); 30 a[i]=a[i-1]^x; 31 } 32 for(int i=1;i<=m;i++){ 33 scanf("%d%d",&q[i].l,&q[i].r); 34 q[i].l--; q[i].id=i; 35 } 36 sort(q+1,q+1+m); 37 int l=1,r=1; 38 cnt[a[1]]=1; 39 for(int i=1;i<=m;i++){ 40 while(r<q[i].r) add(++r); 41 while(r>q[i].r) dec(r--); 42 while(l<q[i].l) dec(l++); 43 while(l>q[i].l) add(--l); 44 out[q[i].id]=now; 45 } 46 for(int i=1;i<=m;i++) printf("%lld ",out[i]); 47 return 0; 48 }