题解-CF617E XOR and Favorite Number

(Large exttt{CF617E})

(small exttt{In my Blog})

这道题其实和P4462几乎一样，但是我却多调了30min，细节很多。洛谷数据太水了QwQ

(large exttt{Meaning})

给定 (n,m,k) ，共 (m) 个询问，每次询问一个区间，问区间内有多少个子区间的异或和等于 (k)。

(large exttt{Solution})

题目中说是区间,则可以转化为前缀和的形式。

令 (S_i=a_1~ exttt{xor}~a_2~ exttt{xor}~...~ exttt{xor}~a_i)

则 (a_l~ exttt{xor}~a_{l+1}~ exttt{xor}~a_{l+2}~...~ exttt{xor}~a_r=S_r~ exttt{xor}~S_{l-1})

然后每次询问就可转化为在 ([l-1,r]) 之间有多少个 (S_i) 和 (S_j) ((ile j)) 使得 (S_i~ exttt{xor}~S_j=k)

发现这个可以用莫队离线下来做，因为 (S_i~ exttt{xor}~S_j=k) 即 (S_i~ exttt{xor}~k=S_j) ， (S_i) 数量改变，答案也就相应改变了。

几个要注意的地方，坑点：

1. 题目中没保证 (k) 不为 (0) ， 即统计贡献的时候要明确，先改贡献，还是先改个数

2. 数组的上界定为 (2e6) 不是 (1e6)， 我也不知道为啥。

然后处理好细节后，就能过了。

(large exttt{Code})

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 2e6; //细节2
inline int read()
{
    register int s = 0;
    register bool neg = 0;
    register char c = getchar();
    for (; c < '0' || c > '9'; c = getchar())
        neg |= (c == '-');
    for (; c >= '0' && c <= '9'; s = s * 10 + (c ^ 48), c = getchar())
        ;
    return (neg ? -s : s);
}

int a, b, c, s[N + 10], bel[N + 10], p[N + 10], ans, Ans[N + 10];
struct node
{
    int l, r, id;
    bool operator<(const node &t) const
    {
        return (bel[l] ^ bel[t.l]) ? bel[l] < bel[t.l] : (bel[l] & 1 ? r < t.r : r > t.r);
    }
} ask[N + 10];

inline void add(int n)
{
    ans += p[(n ^ c)]; //细节1
    p[n]++;
}

inline void del(int n)
{
    p[n]--; //细节1
    ans -= p[(n ^ c)];
}

signed main()
{
    a = read();
    b = read();
    c = read();
    int k = (int)(sqrt(a));
    for (int i = 1; i <= a; i++)
        bel[i] = (i - 1) / k + 1;
    for (int i = 1; i <= a; i++)
        s[i] = (read() ^ s[i - 1]);
    for (int i = 1; i <= b; i++)
    {
        ask[i].l = read() - 1;
        ask[i].r = read();
        ask[i].id = i;
    }
    sort(ask + 1, ask + b + 1);
    // p[0]= 1;
    int l = 1, r = 0; //其实这里左端点必须设为1，如果设为0，则要先将0这个位置计数1.
    for (int i = 1; i <= b; i++)
    {
        while (l < ask[i].l)
            del(s[l++]);
        while (l > ask[i].l)
            add(s[--l]);
        while (r < ask[i].r)
            add(s[++r]);
        while (r > ask[i].r)
            del(s[r--]);
        Ans[ask[i].id] = ans;
    }
    for (int i = 1; i <= b; i++)
        printf("%lld
", Ans[i]);
    return 0;
}