首页 > 其他 > 详细

XOR and Favorite Number CodeForces - 617E -莫队-异或前缀和

时间:2019-01-13 01:25:36      阅读:98      评论:0      收藏:0      [点我收藏+]

标签:per   col   pac   scan   pre   turn   spa   del   %d   

 CodeForces - 617E 

给n个数, m个询问, 每次询问问你[l, r]区间内有多少对(i, j), 使得a[i]^a[i+1]^......^a[j]结果为k。(注意 i ! =  j)
维护一个前缀异或值就可以了。要注意的是 区间[l, r], 我们需要将pre[l-1]......pre[r]都加进去, pre[l-1]不能少。

#include<bits/stdc++.h>
using namespace std;
#define maxn 1234567
#define ll long long
ll s[1<<22],n,m,k,col[maxn],B,sum,ans[maxn],pre[maxn],l,r;
struct node
{
    int l,r,id;
    bool operator<(const node &b)const
    {
        return l/B==b.l/B?r<b.r:l<b.l;
    }
} a[maxn];
void del(int x)
{
    s[pre[x]]--;
    sum-=s[k^pre[x]];
}
void add(int x)
{
    sum+=s[k^pre[x]];
    s[pre[x]]++;
}
int main()
{
    r=-1;
    scanf("%lld%lld%lld",&n,&m,&k);
    for(int i=1; i<=n; i++)
    {
        scanf("%lld",&col[i]);
        pre[i]=pre[i-1]^col[i];
    }
    B=sqrt(n);
    for(int i=0; i<m; i++)
    {
        scanf("%d%d",&a[i].l,&a[i].r);
        a[i].id=i;
        a[i].l--;
    }
    sort(a,a+m);
    for(int i=0; i<m; i++)
    {
        while(l<a[i].l)
            del(l++);
        while(r>a[i].r)
            del(r--);
        while(l>a[i].l)
            add(--l);
        while(r<a[i].r)
            add(++r);
        ans[a[i].id]=sum;
    }
    for(int i=0; i<m; i++)printf("%lld\n",ans[i]);
    return 0;
}

  

XOR and Favorite Number CodeForces - 617E -莫队-异或前缀和

标签:per   col   pac   scan   pre   turn   spa   del   %d   

原文:https://www.cnblogs.com/SDUTNING/p/10261584.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号