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

题意就不再赘述了,二次离线莫队相比于其他莫队,算是细节最多的一种莫队了

思路

首先只考虑增加一个数

若两个数 i,ji,j 的异或和的二进制表示有 kk 个一,我们称之为一个配对

显然,增加一个数对答案的影响为 [L,R][L,R] 与 wR+1w_{R+1} 配对的数的个数

显然,可以用前缀和思想,令 SiS_i 表示前 ii 个数与 wR+1w_{R+1} 配对的数量

那么区间 [L,R][L,R] 的配对数量就为 SR−SL−1S_R-S_{L-1}

然后这个前缀和怎么求?

不妨令 f(i)f(i) 表示前 w1−wiw_1-w_i 中与 wi+1w_{i+1} 配对的个数

g(x)g(x) 表示前 ii 个数中与 xx 配对的数量

f(i)=g(wi+1)f(i)=g(w_{i+1})

考虑 g(x)g(x) 怎么求

因为 0≤k≤140\le k\le14,那么二进制表示下有 kk 个一的个数就为 (14k)\dbinom{14}{k} 最多只有3432个

可以直接暴力求,若令 yiy_i 表示二进制下有 kk 个一的数, 若 xx 与 wk,k∈[1,i]w_k,k\in[1,i] 配对,

则 xx^wk=yiw_k=y_i,那么 x=wkx=w_k^yiy_i,即 g(wkg(w_k^yi)+1y_i)+1,那么我们就可以暴力求出 f(i)f(i)

(这里如果没看懂可以结合下面的代码理解)

那么 SR=f(R)S_R=f(R) 就求出来了,那 SL−1S_{L-1} 又该怎么求?

我们要找 [1,L−1][1,L-1] 与 wR+1w_{R+1} 配对的数量,对于一个询问 [l,r][l,r]

我们要从 R+1R+1 到 rr 每一次都要找一遍对应的 SL−1S_{L-1} 显然在莫队的时候并不好直接求

这时候二次离线的思想就体现出来了,对于 [1,L−1][1,L-1] 中与 wR+1w_{R+1} 的配对数量,

我们要求的是 [R+1,r][R+1,r] 中的数与 [1,L−1][1,L-1] 的配对数量,所以我们将区间记录下来,然后离线再求一遍

这就是二次离线莫队的基本思路.

实现

下面我们讲一下莫队时的具体实现方式

1.右端点增加一个数

答案加上 SR−SL−1S_R-S_{L-1}

SR=f(R)S_R=f(R),记录一下 SL−1S_{L-1} 为求在 [1,L−1][1,L-1] 中与 [R+1,r][R+1,r] 配对的数量

2.右端点删除一个数

答案减去 SR−1−SL−1S_{R-1}-S_{L-1}

SR−1=f(R−1)S_{R-1}=f(R-1),S_{L-1}$ 为求在 [1,L−1][1,L-1] 中与 [r,R−1][r,R-1] 配对的数量

3.左端点增加一个数

答案加上 SR−SL−1S_{R}-S_{L-1}

SL−1=f(L−2)+!kS_{L-1}=f(L-2)+!k,注意这里的 $S(L-2) $表示前 [1,L−1][1,L-1] 中与 wL−1w_{L-1} 配对的数量,

而 f(L−2)f(L-2) 表示的是 [1,L−2][1,L-2] 中与 wL−1w_{L-1} 配对的数量,所以需要特判一个 wL−1w_{L-1},

而只有当 k=0k=0 时,wL−1w_{L-1} 才会与自己配对,所以加个 !k!k

SRS_{R} 为求[1,R] 中与 [l,L−1][l,L-1] 配对的数量

4.左端点删除一个数

答案减去 SR−SLS_{R}-S_{L}
SL=f(L−1)+!kS_L=f(L-1)+!k,SRS_R 为求 [1,R][1,R] 中与 [L+1,l][L+1,l] 配对的数量

紧接着对于未处理的所有询问,对于每一个 [1,i],i∈[1,n][1,i],i\in[1,n],暴力求出每个区间需要求的询问

求完了过后,记得前缀和累加一下,因为我们莫队每次处理的是增量,并不是答案

结合代码理解

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
#include<algorithm>
#define get(x) ((x) / len)
using namespace std;
const int N = 1e5 + 5;
typedef long long ll;

ll ans[N];
int w[N], g[N], f[N], len;
struct query1
{
    int id, l, r;
    ll res;
    bool operator < (const query1 a) const
    {
        int x = get(l), y = get(a.l);
        if (x != y) return x < y;
        return r < a.r;
    }
} q[N];
struct query2
{
    int id, l, r, t;
};
vector<query2> rang[N];
vector<int> num;

int get_count(int x)
{
    int res = 0;
    while (x)
        res += x & 1, x >>= 1;
    return res;
}

int main()
{
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= n; i++)
        scanf("%d", &w[i]);
    for (int i = 1; i <= m; i++)
        scanf("%d%d", &q[i].l, &q[i].r), q[i].id = i;
    for (int i = 0; i < 1 << 14; i++)
        if (get_count(i) == k)
            num.push_back(i);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < num.size(); j++)
            g[w[i] ^ num[j]]++;
        f[i] = g[w[i + 1]];
    }
    len = sqrt(n);
    sort(q + 1, q + 1 + m);
    for (int i = 1, l = 1, r = 0; i <= m; i++)
    {
        int L = q[i].l, R = q[i].r;
        if (r < R) rang[l - 1].push_back(query2({i, r + 1, R, -1}));
        while (r < R) q[i].res += f[r++];
        if (r > R) rang[l - 1].push_back(query2({i, R + 1, r, 1}));
        while (r > R) q[i].res -= f[r - 1], r--;
        if (l < L) rang[r].push_back(query2({i, l, L - 1, -1}));
        while (l < L) q[i].res += f[l - 1] + !k, l++;
        if (l > L) rang[r].push_back(query2({i, L, l - 1, 1}));
        while (l > L) q[i].res -= f[l - 2] + !k, l--;
    }
    memset(g, 0, sizeof(g));
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < num.size(); j++)
            g[w[i] ^ num[j]]++;
        for (int j = 0; j < rang[i].size(); j++)
        {
            query2& a = rang[i][j];
            int l = a.l, r = a.r, t = a.t, id = a.id;
            for (int x = l; x <= r; x++)
                q[id].res += g[w[x]] * t;
        }
    }
    for (int i = 1; i <= m; i++)
        q[i].res += q[i - 1].res, ans[q[i].id] = q[i].res;
    for (int i = 1; i <= m; i++)
        printf("%lld\n", ans[i]);
    return 0;
}