Codeforces 617E XOR and Favorite Number

题目链接http://codeforces.com/contest/617/problem/E

题意:给定一个序列和若干询问,每次询问[L,R]内满足条件的点对(i,j),条件是[i,j]的异或和等于k

思路:对原序列求一下前缀异或和后,对于要的区间可以直接差分出来,然后就可以上莫队了,开个大点的桶记录x出现的次数,转移O(1),每次转移的时候更新答案即加上或减去cnt[xxork],时间复杂度O((n+m)\sqrt n)。需要注意的时候查询区间范围要改成[L-1,R],因为差分的缘故。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=100000+10;
const int M=1000000+10;
int n,m,k,i,l,r,sz,a[N],block[N],cnt[M*2];
ll ans[N],res;
struct Query{
    int l,r,id;
    bool operator<(const Query&rhs)const{
        return block[l]^block[rhs.l]?block[l]<block[rhs.l]:block[l]&1?r<rhs.r:r>rhs.r;
    }
}q[N];
void ins(int x){
    res+=cnt[x^k];
    cnt[x]++;
}
void dec(int x){
    cnt[x]--;
    res-=cnt[x^k];
}
int main(){
    read(n),read(m),read(k);
    sz=sqrt(n+1+0.5);
    block[1]=(1-1)/sz;
    for (i=2;i<=n+1;i++) read(a[i]),a[i]^=a[i-1],block[i]=(i-1)/sz;
    for (i=1;i<=m;i++){
        read(q[i].l),read(q[i].r),q[i].r++;
        q[i].id=i;
    }
    sort(q+1,q+1+m);
    for (l=i=1,r=0;i<=m;i++){
        int L=q[i].l,R=q[i].r;
        while (r<R) ins(a[++r]);
        while (l>L) ins(a[--l]);
        while (r>R) dec(a[r--]);
        while (l<L) dec(a[l++]);
        ans[q[i].id]=res;
    }
    for (i=1;i<=m;i++) printf("%lld\n",ans[i]);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注