Codeforces617E【莫队算法+前缀异或】

题意：

给出一系列数，对每个查询区间，计算有多少个子区间异或为k。

思路：

可以先预处理异或前缀，一个区间[L,R]的异或值=sum[R]^sum[L-1];

如果当前区间是[a,b]，加一个右端点b+1，那么这个b+1的贡献就是[a,b]区间内有多少个sum[x]=sum[b+1]^k

那么我们可以每次记录num[sum[x]]即num[sum[b+1]^k]，并记录num[sum[b+1]]++，同理左区间。

那么我们就可以使用莫队算法。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

typedef pair<int,int> PII;

const int N=2e6+10;

int sum[N],pos[100010];

LL num[N];

int n,m,k,x;

struct asd{

    int left,right,id;

    LL res;

}e[100010];

bool cmp(asd x,asd y)

{

    if(pos[x.left]==pos[y.left]) return x.right<y.right;

    return pos[x.left]<pos[y.left];

}

LL ans; //答案遵守ans先加，再变；先变，ans再减；

void solve()

{

    sort(e,e+m,cmp);

    ans=0;

    memset(num,0,sizeof(num));

    int L=0,R=0;

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

    {

        while(L<e[i].left-1)                         //当他在区间左边，他要减去他产生右端

        {

            num[sum[L]]--;                            //先变

            ans-=num[sum[L]^k];               //答案再减

            L++;

        }

        while(L>=e[i].left)                      //当他在区间右边，他要加上他右端

        {

            L--;

            ans+=num[sum[L]^k];          //先加答案

            num[sum[L]]++;                      //再变

        }

        while(R<=e[i].right)                //小于，要加左边

        {

            ans+=num[sum[R]^k];        //先加答案

            num[sum[R]]++;                   //再变

            R++;

        }

        while(R>e[i].right+1)               //大，要减左

        {

            R--;

            num[sum[R]]--;                      //先变

            ans-=num[sum[R]^k];         //再减答案

        }

        e[e[i].id].res=ans;

    }

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

        printf("%lld\n",e[i].res);

}

int main()

{

    scanf("%d%d%d",&n,&m,&k);

    sum[0]=0;

    int block=(int)sqrt(n);

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

    {

        scanf("%d",&x);

        sum[i]=sum[i-1]^x;

        pos[i]=(i-1)/block+1;

    }

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

    {

        scanf("%d%d",&e[i].left,&e[i].right);

        e[i].id=i;

    }

    solve();

    return 0;

}

/*

6 2 3

1 2 1 1 0 3

1 6

3 5

5 3 1

1 1 1 1 1

1 5

2 4

1 3

*/

巴特西

Codeforces617E【莫队算法+前缀异或】

最新文章

热门文章