P4462-题解

· · 题解

题意简述

传送门。

给定一个长度为 n 的序列 a，有 m 个询问，每次给出一个区间 [L,R]，求出区间内有多少个子区间异或和为指定的 k。

数据范围：1\le n,m,a_i,k\le 10^5。

思路分析

前置知识：莫队。

在此之前，我们要先知道异或运算是个什么东西：就是将两个二进制数的最低位对其，依次比较两个二进制数的每一位，如果相同，则得到的结果为 0，不同则为 1。

从定义可以推导出来的结论：对于任意 x，都有 x\oplus x=0，应为两个相同的数二进制上每一位都相同，所以结果一定为 0，同理可以推出 x\oplus 0=x。这里不多做叙述。（\oplus 为异或的运算符号）

我们定义 s_i=a_1\oplus a_2\oplus\dots\oplus a_i 。显然 a_l\oplus a_{l+1}\oplus\dots\oplus a_r=s_r\oplus s_{l-1}。基于的原理便是 x\oplus x=0。应为 s_r,s_{l-1} 都包含 s_{l-1} 这个部分，所以相抵消，只剩下 [l,r] 这部分的异或和。

根据异或的定义，我们可以很方便的推出：如果 a\oplus b=k，那么 a\oplus k=b,b\oplus k=a。

结论部分讲解完毕，让我们回到题面，注意到是区间静态问题，不要求强制在线，显然可以用莫队乱搞。

我们在上文提到 s_r\oplus s_{l-1} 即为 [l,r] 区间的异或和。可以将问题转化为：每次给出区间 [L,R]，求出 \sum\limits_{L-1\le i,j\le R}[s_i\oplus s_j=k]。我们可以开一个桶 cnt，cnt_{s_i} 为当前区间中，s_i 的个数。当前区间异或和为 k 的子区间数量为 ans。

如果有 s_i\oplus s_j=k，那么必然 s_i\oplus k=s_j。如果当前区间左右边界移动时，区间内多了一个 s_i，那么该区间内所有的 s_j 与其的异或和是 k，区间内 s_j 的数量为 cnt_{s_j}，所以对当前区间答案的贡献为 cnt_{s_j}。在将 cnt_{s_i}+1。我们就完成了区间的扩张。

已知 s_i,k，如何快速找到 s_j 使得 s_i\oplus s_j=k。根据异或运算的性质 s_j=s_i\oplus k。

坑点大全：

  1. 因为询问是区间 [L,R]，而处理时会将 L-1。所以会出现左边界为 0 的情况。因此莫队中两个指针的初始位置都是 0.

  2. 初始情况下，区间包含 s_0=0，所以 cnt_0 初值为 1。

  3. 当 k=0 时，对于任何 a 都有 a\oplus 0=a。因此在删除时，应当先对 cnt 操作，再对答案 ans 操作（我 WA 了好几次）。

  4. 虽然 a_i 小于 10^5，但如果 a_1=100000,a_2=31071，s_2 有最大值为 377777。所以 cnt 的大小一定要把控好（好像数据不卡这个）。

莫队是什么大家应该也知道吧，毕竟我都讲完了。

Code

码风不好，勿抄。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int N=4e5+10;
typedef long long ll;
ll n,m,k,a[N],t,cnt[N],ans,ql,qr,l,r,res[N];
struct node{
    ll l,r,idx;
}b[N];
inline void read(ll &x){
    char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return;
}
inline void write(ll x){
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
bool cmp(node a,node b){
    return (a.l/t)^(b.l/t)?a.l<b.l:((a.l/t)&1?a.r<b.r:a.r>b.r);//常数优化
}
inline void add(int x){
    ans+=cnt[a[x]^k];
    cnt[a[x]]++;

}
inline void del(int x){
    cnt[a[x]]--;//如果你100pts，但 Unaccepted，你很可能错这里了。一定要先修改cnt再修改ans.具体可以看我上面说的坑点（第3条）。
    ans-=cnt[a[x]^k];
}
int main(){
    read(n),read(m),read(k);t=sqrt(n);
    for(int i=1;i<=n;i++)read(a[i]),a[i]^=a[i-1];
    for(int i=1;i<=m;i++)read(b[i].l),read(b[i].r),b[i].l--,b[i].idx=i;
    sort(b+1,b+1+m,cmp);
    cnt[0]=1;
    for(int i=1;i<=m;i++){
        ql=b[i].l,qr=b[i].r;
        while(l<ql)del(l++);
        while(l>ql)add(--l);
        while(r<qr)add(++r);
        while(r>qr)del(r--);
        res[b[i].idx]=ans;
    }
    for(int i=l;i<=m;i++){
        write(res[i]);putchar('\n');
    }
    return 0;
}

AC 记录。

如有错误，请指出。