Loj 2534 异或序列

Loj 2534 异或序列

• 考虑莫队离线处理.每加一个数,直接询问 \(a[x]\oplus k\) 的前/后缀数目即可,减同理.
• 利用异或的优秀性质,可以维护异或前缀和,容易做到每次 \(O(1)\) 移动区间端点.

很久没写莫队了.有一个小细节开始写错了:如果 \(a.belong\) 是根据 \(a.l\) 算出的,排序时的第二关键字就选取 \(a.r\) ,否则会被卡到 \(O(n^2)\) .

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pii pair<int,int>
inline int read()
{
    int x=0;
    bool pos=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar())
        if(ch=='-')
            pos=0;
    for(;isdigit(ch);ch=getchar())
        x=x*10+ch-'0';
    return pos?x:-x;
}
const int MAXN=1e5+10,N=2e5;
struct query{
    int l,r,bel;
    int ans,id;
}q[MAXN];
bool cmp1(query a,query b)
{
    if(a.bel!=b.bel)
        return a.bel<b.bel;
    if(a.r!=b.r)
        return a.r<b.r;
    return a.l<b.l; 
}
bool cmp2(query a,query b)
{
    return a.id<b.id;
}
int n,m,k;
int ans=0;
int a[MAXN],pre[MAXN],cnt[MAXN<<1];
void Add(int x)
{
    ans+=cnt[k^pre[x]]; 
    ++cnt[pre[x]];
}
void Remove(int x)
{
    --cnt[pre[x]];
    ans-=cnt[k^pre[x]];
}
int main()
{
    n=read(),m=read(),k=read();
    int bsiz=sqrt(n);
    for(int i=1;i<=n;++i)
        a[i]=read(),pre[i]=pre[i-1]^a[i];
    for(int i=1;i<=m;++i)
        {
            q[i].l=read(),q[i].r=read();
            q[i].bel=(q[i].l-1)/bsiz;
            q[i].id=i;
        }
    sort(q+1,q+1+m,cmp1);
    int L=1,R=0;
    for(int i=1;i<=m;++i)
        {
            int l=q[i].l,r=q[i].r;
            while(L<l-1)
                Remove(L++);
            while(L>l-1)
                Add(--L);
            while(R<r)
                Add(++R);
            while(R>r)
                Remove(R--);
            q[i].ans=ans;
        }
    sort(q+1,q+1+m,cmp2);
    for(int i=1;i<=m;++i)
        printf("%d\n",q[i].ans);
    return 0;
}

Loj 2534 异或序列

原文：https://www.cnblogs.com/jklover/p/10437478.html