M_sea

洛谷4462 [CQOI2018]异或序列
LuoguBZOJ分析记 $s[i]=a[1]\oplus a[2]\oplus ... \oplus a[i]$...
扫描右侧二维码阅读全文
15
2019/03

洛谷4462 [CQOI2018]异或序列

Luogu

BZOJ

分析

记 $s[i]=a[1]\oplus a[2]\oplus ... \oplus a[i]$ 。

问题变为 $[l-1,r]$ 中,有多少对 $(x,y)$ 满足 $s[x]\oplus s[y]=k$ 。

莫队即可。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

struct query { int l,r,id; } q[N];
int block;
inline int cmp(query a,query b) {
    if ((a.l/block)^(b.l/block)) return a.l<b.l;
    else if ((a.l/block)&1) return a.r<b.r;
    else return a.r>b.r;
}

int n,m,k,ans;
int a[N],cnt[N<<1],Ans[N];

inline void add(int x) { ans+=cnt[x^k],++cnt[x]; }
inline void del(int x) { --cnt[x],ans-=cnt[x^k]; }

int main() {
    n=read(),m=read(),k=read(); block=sqrt(n);
    for (re int i=1;i<=n;++i) a[i]=read()^a[i-1];
    for (re int i=1;i<=m;++i) q[i].l=read()-1,q[i].r=read(),q[i].id=i;
    sort(q+1,q+m+1,cmp); int l=1,r=0;
    for (re int i=1;i<=m;++i) {
        while (l<q[i].l) del(a[l]),++l;
        while (l>q[i].l) --l,add(a[l]);
        while (r<q[i].r) ++r,add(a[r]);
        while (r>q[i].r) del(a[r]),--r;
        Ans[q[i].id]=ans;
    }
    for (re int i=1;i<=m;++i) printf("%d\n",Ans[i]);
    return 0;
}
最后修改:2019 年 05 月 26 日 09 : 12 PM

发表评论