【洛谷P4462】异或序列

时间：2021-09-01 05:47:14

题目大意：给定一个长度为 N 的序列，有 M 组询问，每组询问查询区间 [l,r] 内异或和等于给定常数 K 的区间组数。

题解：对于异或和问题，一般先进行前缀和处理，转化为两个点的的关系。因此，经过前缀和处理后，询问变成了在给定区间内，查询二元组 \((i,j)\) 满足 \(a[i]\oplus a[j]=k\) 的个数。从值域角度进行考虑，每次加入一个值时，将满足条件的值加入答案贡献即可，因此可以使用莫队处理。

代码如下

#include <bits/stdc++.h>

#define fi first

#define se second

#define pb push_back

#define mp make_pair

#define all(x) x.begin(),x.end()

#define cls(a,b) memset(a,b,sizeof(a))

using namespace std;

typedef long long ll;

typedef pair<int,int> P;

const int dx[]={0,1,0,-1};

const int dy[]={1,0,-1,0};

const int mod=1e9+7;

const int inf=0x3f3f3f3f;

const int maxn=1e5+10;

const double eps=1e-6;

inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

inline ll sqr(ll x){return x*x;}

inline ll fpow(ll a,ll b,ll c){ll ret=1%c;for(;b;b>>=1,a=a*a%c)if(b&1)ret=ret*a%c;return ret;}

inline ll read(){

    ll x=0,f=1;char ch;

    do{ch=getchar();if(ch=='-')f=-1;}while(!isdigit(ch));

    do{x=x*10+ch-'0';ch=getchar();}while(isdigit(ch));

    return f*x;

}

/*------------------------------------------------------------*/

int n,m,k,a[maxn];

int cnt[maxn*10],l=1,r=0,tot;

ll ans[maxn],now;

struct query{int id,l,r,bl;}q[maxn];

inline int get(int pos){return (pos-1)/tot+1;}

bool cmp(const query &x,const query &y){

    return x.bl!=y.bl?x.bl<y.bl:(x.bl&1)?x.r<y.r:x.r>y.r;

}

void read_and_parse(){

    n=read(),m=read(),k=read(),tot=sqrt(n);

    for(int i=1;i<=n;i++)a[i]=read();

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

    for(int i=1;i<=m;i++){

        int l=read(),r=read();

        q[i].id=i,q[i].l=l-1,q[i].r=r,q[i].bl=get(q[i].l);

    }

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

}

void update(int pos,int f){

    if(f==1){

        now+=cnt[a[pos]^k];

        ++cnt[a[pos]];

    }else{

        --cnt[a[pos]];

        now-=cnt[a[pos]^k];

    }

}

void solve(){

    for(int i=1;i<=m;i++){

        while(r<q[i].r)update(++r,1);

        while(r>q[i].r)update(r--,-1);

        while(l<q[i].l)update(l++,-1);

        while(l>q[i].l)update(--l,1);

        ans[q[i].id]=now;

    }

    for(int i=1;i<=m;i++)printf("%lld\n",ans[i]);

}

int main(){

    read_and_parse();

    solve();

    return 0;

}

相关文章