[bzoj5301][Cqoi2018]异或序列_莫队

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

异或序列 bzoj-5301 Cqoi-2018

题目大意 ：题目链接。

注释：略。

想法：

由于a^a=0这个性质，我们将所有的数变成异或前缀和。

所求就变成了求所有的$l_i\le x<y\le r_i$使得$bfr_x^bfr_y=k$。

又因为如果$bfr_x^bfr_y=k$，则$bfr_x=bfr_y^x$。

所以用桶维护即可。

最后，附上丑陋的代码... ...

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#define N 100010

using namespace std; int bfr[N],stack[N<<5],blg[N],k; int n,m;

typedef long long ll; ll Ans[N],ans;

struct Node {int l,r,id;}a[N]; inline bool cmp(const Node &x,const Node &y) {return blg[x.l]==blg[y.l]?x.r<y.r:blg[x.l]<blg[y.l];}

inline char nc() {static char *p1,*p2,buf[100000]; return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}

int rd() {int x=0; char c=nc(); while(!isdigit(c)) c=nc(); while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=nc(); return x;}

inline void add(int val)

{

    ans+=stack[k^val];

    stack[val]++;

}

inline void del(int val)

{

    stack[val]--;

    ans-=stack[val^k];

}

int main()

{

    n=rd(),m=rd(); k=rd(); int unit=sqrt(n); int t=n/unit;

    for(int i=1;i<=t;i++)

    {

        for(int j=(i-1)*unit+1;j<=i*unit;j++) bfr[j]=rd(),bfr[j]^=bfr[j-1],blg[j]=i;

    }

    if(t*unit<n)

    {

        t++;

        for(int i=(t-1)*unit+1;i<=n;i++) bfr[i]=rd(),bfr[i]^=bfr[i-1],blg[i]=t;

    }

    // stack[0]=1;

    for(int i=1;i<=m;i++) a[i].l=rd(),a[i].r=rd(),a[i].id=i,a[i].l--;

    sort(a+1,a+m+1,cmp); ans=0;

    int point_l=0,point_r=-1;

    // for(int i=point_l;i<=point_r;i++) add(bfr[i]); Ans[a[1].id]=ans;

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

    {

        while(point_l<a[i].l) del(bfr[point_l]),point_l++;

        while(point_l>a[i].l) point_l--,add(bfr[point_l]);

        while(point_r>a[i].r) del(bfr[point_r]),point_r--;

        while(point_r<a[i].r) point_r++,add(bfr[point_r]);

        Ans[a[i].id]=ans;

    }

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

    return 0;

}