P4462题解

Deamer · 2023-07-25 20:26:17 · 题解

闲话：

在这篇题解中你会看到一些题解被 hack。
在这篇题解中你会知道 Del 和 Add 函数正确顺序和一些难理解东西的原理。
在这片题解中你会看见很多作者自己踩过的坑。

正文：

我们可以维护异或前缀和，那么 l 到 r 的异或和就为 a_l-1 \bigoplus a_r，问题就变成了询问区间 [l-1 , r] 中，有多少对 l 和 r 满足 a_{l-1} \bigoplus a_r = k。

我们对于每个值，用莫队维护它出现的次数和在它之前满足与这个值异或起来为 k 的数的个数，添加或删除点时答案对应加上或减去维护的个数即可。

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const int N=1e5+10,M=2e5+10;
int n,m,c;
int a[N];
struct Query { int l,r,id; } q[N];
int block;
int bel[N];
ll sum;
int tot[M];
ll ans[N];

bool cmp(Query a,Query b){
    return (bel[a.l]^bel[b.l]) ? bel[a.l]<bel[b.l] : ( (bel[a.l]&1) ? a.r<b.r : a.r>b.r ) ;
}

void Build(){
    block=pow(n,2.0/3.0);
    for(int i=1;i<=n;i++) bel[i]=(i-1)/block+1;
}

void Add(int x) { sum+=tot[a[x]^c]; tot[a[x]]++; }

void Del(int x) { tot[a[x]]--; sum-=tot[a[x]^c]; }

int main(){
    scanf("%d%d%d",&n,&m,&c);
    Build();
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) a[i]^=a[i-1];
    for(int i=1;i<=m;i++){
        scanf("%d%d",&q[i].l,&q[i].r);
        q[i].id=i;
    }
    sort(q+1,q+1+m,cmp);
    tot[0]=1;
    int l=0,r=0;
    for(int i=1;i<=m;i++){
        int ql=q[i].l-1,qr=q[i].r,id=q[i].id;
        while(l<ql) Del(l++);
        while(l>ql) Add(--l);
        while(r<qr) Add(++r);
        while(r>qr) Del(r--);
        ans[id]=sum;
    }
    for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);
    return 0;
}

说几个坑点和不好理解的点吧 :

tot[0]=1 : 由于询问是对于区间 [l-1,r] 的，所以询问范围为 [0,n]，又因为 a_0=0，所以要写上这句话，不然对于异或前缀和为 k 的位置，显然有一个合法区间 [1,x]，其所对应的 l 为 0，但由于 tot_0=0，没有统计答案。
l=0 : 由于询问范围为 [0,n]，自然 l 初始值为 0 （这个 shaber 因为这个调了半天）。
ql=q[i].l-1 : 由于询问是对于区间 [l-1,r]。
void Add(int x) { sum+=tot[a[x]^c]; tot[a[x]]++; } : 由于询问是对于区间 [l-1,r] 的，且 l≤r，所以在异或前缀和数组中这一定是两个位置，如果先写第二句话的话，当 k=0 时，sum 在统计答案时会会把当前位置算进当前位置的答案中加上，显然不合法，于是多算答案。
void Del(int x) { tot[a[x]]--; sum-=tot[a[x]^c]; } : 其实大致思路同上一条，由于询问是对于区间 [l-1,r] 的，且 l≤r，所以在异或前缀和数组中这一定是两个位置，如果先写第二句话的话，当 k=0 时，sum 在统计答案时会把当前位置算进当前位置的答案中减去，显然不合法，于是少算答案。
tot[200010] 由于异或前缀和可能大于 n，最大值为 2^{17}-1=131071，故开这么大。
由于是区间数量，记得开 long long。

对于上文第五条错误 hack :

4 1 0
0 1 0 1
2 4

正确输出 :

错误输出 :

对于上文第八条错误 hack : (叉了6篇)

100000 1 0
(100000个0)
1 100000

正确输出 :

5000050000

错误输出 :

705082704

数组越界应该不用我说怎么卡了吧 qwq （其实我也不会

有错误请及时回复或私信我，谢谢啦！

写在最后：希望被 hack 的题解不要只改了代码，不写明原理，只是说 “脑抽了” 之类的话。

Upd : 11.22 改了评论区指出的错误