题解：P4887 【模板】莫队二次离线（第十四分块(前体)）

· · 题解

题解

这里提供一种不需要考虑 k 的做法，非常直观。

对于莫队二次离线，我们考虑每次只记录答案的变化量，那么莫队时我们只要知道这个数能和区间里的多少个数匹配即可。发现他是可差分的，于是设其为 f(i,j) 表示 a_i 能和 [1,j] 中的哪些数匹配，g(i,j) 表示 a_i 能和 [j,n] 中的哪些数匹配。

那么左端点移动时答案的变化量即为 g(L,L)-g(L,R+1)；右端点移动时即为 f(R,R)-f(R,L-1)。发现两个式子的前面那项可以直接预处理，后面的项我们可以直接把他分别离线到 R+1 和 L-1 处理。

又因为 f 是前缀，g 是后缀，所以要从前往后和从后往前扫两遍。这样实际上保证了一定不会在 k=0 的时候算重即贡献区间重复。

但这样我们会离线下来 m\sqrt n 个询问，有可能会爆空间。考虑莫队每次指针的移动是连续的，所以只要存下左右端点即可。

那么问题就转化成了每次加一个数，再询问另一个数能与前面加的多少个数匹配。考虑使用异或的性质，即：a ⊕b=k\to a⊕k=b。

于是开一个桶，每次加入一个数 a 的时候把所有二进制位下有 k 个 1 的 b，s_{a⊕b}\gets s_{a⊕b}+1。查询直接查 s_x 即可，这么做显然不会算重。

因为我们算的是变化量，最后再求个前缀和才是最终答案。

AC_Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 10, M = 16384;
int n, m, k, t[M], a[N], s1[N], s2[N], ans[N], len, pos[N];
vector<int> num;
struct node{int l, r, op, id;}q[N];
vector<node> G[N], H[N];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m >> k;
    len = sqrt(n);
    for(int i = 0; i < M; i ++)if(__builtin_popcount(i) == k)num.push_back(i);
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
        pos[i] = i / len;
        s1[i] = s1[i - 1] + t[a[i]];
        for(auto j : num)t[a[i] ^ j] ++;
    }
    memset(t, 0, sizeof t);
    for(int i = n; i >= 1; i --){
        s2[i] = s2[i + 1] + t[a[i]];
        for(auto j : num)t[a[i] ^ j] ++;
    }
    for(int i = 1; i <= m; i ++){
        cin >> q[i].l >> q[i].r;
        q[i].id = i;
    }
    sort(q + 1, q + 1 + m, [](auto a, auto b){
        if(pos[a.l] == pos[b.l])return a.r < b.r;
        else return pos[a.l] < pos[b.l];
    });
    int l = 1, r = 0;
    for(int i = 1; i <= m; i ++){
        if(r < q[i].r)ans[q[i].id] += s1[q[i].r] - s1[r], G[l].push_back({r + 1, q[i].r, -1, q[i].id}), r = q[i].r;
        if(r > q[i].r)ans[q[i].id] -= s1[r] - s1[q[i].r], G[l].push_back({q[i].r + 1, r, 1, q[i].id}), r = q[i].r;
        if(l < q[i].l)ans[q[i].id] -= s2[l] - s2[q[i].l], H[r].push_back({l, q[i].l - 1, 1, q[i].id}), l = q[i].l;
        if(l > q[i].l)ans[q[i].id] += s2[q[i].l] - s2[l], H[r].push_back({q[i].l, l - 1, -1, q[i].id}), l = q[i].l;
    }
    memset(t, 0, sizeof t);
    for(int i = 1; i <= n; i ++){
        for(auto j : G[i])for(int k = j.l; k <= j.r; k ++)ans[j.id] += j.op * t[a[k]];
        for(auto j : num)t[a[i] ^ j] ++;
    }
    memset(t, 0, sizeof t);
    for(int i = n; i >= 1; i --){
        for(auto j : H[i])for(int k = j.l; k <= j.r; k ++)ans[j.id] += j.op * t[a[k]];
        for(auto j : num)t[a[i] ^ j] ++;
    }
    for(int i = 1; i <= m; i ++)ans[q[i].id] += ans[q[i - 1].id];
    for(int i = 1; i <= m; i ++)cout << ans[i] << '\n';
    return 0;
}

完结撒花。