『分块·莫队基础』[codeforces 617E]XOR and Favorite Number

题目描述

dydxh又没有强制在线，于是mzx又可以开心地水过了，不过他发现，在线貌似不可做？

给定长度为n的数列以及正整数，有m个询问每次询问给定两个数l,r，求$l\le i\le j\le r$，且$a(i)xora(i+1)xora(i+2)xor...xora(j)=k的(i,j)$的个数。

题解

根据莫队算法的原理，我们应该讲每一个询问进行分块。分块的方法是：将一个长度为$n$的序列分成$\sqrt{n}$块，若询问的左端点在相同的块上，就根据右端点从小到大排序；否则按左端点的块进行从小到大排序。

然后再回到此题，我们需要找到$S_{l}xorSr=k$中有多少对$(l,r)$.显然$q_i.l\le q_i.r$.$S_i$表示原序列中前$i$个数的异或和。

假设我们已经知道了$(l,r)$的答案，我们如何更新其它的答案呢：

• 更新区间$(l+1,r)$,那么合法的左区间位置由$[l?1,r?1]$变成了$[l,r]$,因此减去第$l?1$个位置的影响即可。
• 跟新区间$(l?1,r)$,那么合法的左区间位置由$[l?1,r?1]$变成了$[i?2,r?1]$,添加第$l?2$个位置的影响即可。
• 右区间的更新方式同理。

还有一个值得注意的地方：当$k=0$且在执行某一个删除操作的时候，会多减一个自己本身产生的影响；所以每一次进行删除操作得时候，便需要重新对答案进行$+1$操作才行。

代码如下：

#include <bits/stdc++.h>
#define int long long
using namespace std;int n,m,k,T;
struct node
{
    int l,r,id,p;friend bool operator < (node p1, node p2) {
    if (p1.p == p2.p) return p1.r < p2.r;return p1.p < p2.p;}
} q[200000];
int ans = 0;
int a[200000];
int Ans[200000];
int cnt[2000000];inline int read(void)
{
    int s = 0, w = 1;char c = getchar();while (c<'0' || c>'9') {
    if (c == '-') w = -1; c = getchar();}while (c>='0' && c<='9') s = s*10+c-48,c = getchar();return s*w;
}void init(void)
{
    n = read(), m = read(), k = read(), T = sqrt(n);for (int i=1;i<=n;++i) a[i] = read(), a[i] = a[i-1] ^ a[i];for (int i=1;i<=m;++i) {
    q[i].l = read();q[i].r = read();q[i].id = i;q[i].p = (q[i].l + T - 1) / T;//表示第i个询问所属的块的编号}sort(q+1, q+m+1);return;
}void change(int x,int del)
{
    ans += cnt[x ^ k] * del;cnt[x] += del;if (del == -1 && k == 0) ans ++;return;
}void work(void)
{
    int L , R;L = R = 1;cnt[a[1]] ++;cnt[0] ++;ans = (a[1] == k);for (int i=1;i<=m;++i){
    while (L < q[i].l) change(a[L-1],-1), L ++;while (L > q[i].l) L --, change(a[L-1],1);while (R > q[i].r) change(a[R],-1), R --;while (R < q[i].r) R ++, change(a[R],1);Ans[q[i].id] = ans;}for (int i=1;i<=m;++i) printf("%lld\n", Ans[i]);return;
}signed main(void)
{
    freopen("2011.in","r",stdin);freopen("2011.out","w",stdout);init();	work();return 0;
}