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

· · 题解

学习了二次离线。

下文默认 n,m 同阶。

题意自己看。

首先我们知道这个题是没有修改的，所以我们考虑莫队。

然而因为莫队加点删点的复杂度太高了（要在这个同时维护答案），所以这是过不去的。

回想莫队的过程，莫队分为两个部分，加点删点（下称修改），以及在插入的时候更新答案（下称查询）。

那么你会发现普通莫队是有 O(n\sqrt{n}) 次修改和 O(n\sqrt{n}) 次查询的，这不太好。

考虑莫队的本质，左右端点的移动对应了区间的拓展与收缩，考虑移动一个端点对答案的影响。

令 f(i,[l,r]) 表示 i 对 [l,r] 这段区间的贡献。

那么我们假设在莫队移动指针的时候是增加了右端点，那么我们就是要求出：

\sum_{i=r+1}^{r+k} f(i,[l,i-1])

这就是从莫队的上一次的指针区间到这一次的指针区间答案的增量。

你发现这个题的贡献是可以差分的，所以你可以做一个转化，f(i,[l,i-1])=f(i,[1,i-1])-f(i,[1,l-1])。

你发现前半部分只和 i 相关，可以一开始预处理出来。

然后后半部分，你发现这是一个点对一段前缀的贡献，考虑对前缀扫描线，然后在遍历所有点 i 算出带来的贡献即可。

剩下的三种莫队指针移动也是同理。

考虑复杂度分析，你发现我们的查询次数还是 O(n\sqrt{n})，但修改次数被降至了 O(n)（仅在扫描线时修改）。

现在就有不平衡的情况出现了，考虑用一些东西平衡复杂度，在别的二离题中常见的是用 O(\sqrt{n}) 修改，O(1) 查询的各种分块来平衡复杂度。

对于本题，我们考虑一个异或的性质，a \oplus b=c 等价于 a \oplus c=b。所以我们可以预处理出所有二进制下有 k 个 1 的数，然后修改时暴力所有二进制下有 k 个 1 的数更新答案即可。

注意，我们莫队求得的是答案增量，所以最后要做一遍前缀和才能得到真正的答案。

令 V 为值域大小，则我们做到了查询复杂度 O(1)，修改复杂度 O(\dbinom{\log V}{k})。

那么总时间复杂度 O(n\dbinom{\log V}{k}+n\sqrt{n})，可以通过。

还有一些细节见代码。

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define rep(i , l, r) for(int i = l;i <= r;i++)
#define per(i , l , r) for(int i = l;i >= r;i--)
const int N = 1e5 + 5;
int len , a[N] , ct[N] , nw[N];
vector<int>tp;
struct sb{
    int  l, r , id , ans;
    bool operator <(const sb &c) const{
        return l / len ^ c.l / len ? l / len < c.l / len : r / len < c.r / len;
    }
} q[N];
struct jb{
    int l , r , id , fg , ii;
    bool operator <(const jb&c) const{
        return ii < c.ii;
    }
};
int tott;
jb c[N << 2];
// vector<jb> c[N];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0) , cout.tie(0);
    int n , m , k;
    cin >> n >> m >> k;
    rep(i , 0 , 16383) if(__builtin_popcount(i) == k) tp.push_back(i);
    rep(i , 1 , n){
        cin >> a[i];
        nw[i] = ct[a[i]];
        for(auto v : tp) ct[a[i] ^ v]++;
    }
    memset(ct , 0 , sizeof(ct));
    rep(i , 1 , m) cin >> q[i].l >> q[i].r , q[i].id = i;
    len = n / sqrt(m);
    sort(q + 1 , q + m + 1);
    int l = 1 , r = 0;
    rep(i , 1 , m){
        if(l > q[i].l) c[++tott] = {q[i].l , l - 1 , i , 1 , r};
        while(l > q[i].l) q[i].ans -= nw[--l];
        if(r < q[i].r) c[++tott] = {r + 1 , q[i].r , i , -1 , l - 1};
        while(r < q[i].r) q[i].ans += nw[++r];
        if(l < q[i].l) c[++tott] = {l , q[i].l - 1 , i , -1 , r};
        while(l < q[i].l) q[i].ans += nw[l++];
        if(r > q[i].r) c[++tott] = {q[i].r + 1 , r , i , 1 , l - 1};
        while(r > q[i].r) q[i].ans -= nw[r--];
    }
    sort(c + 1 , c + tott + 1);
    int jj = 1;
    rep(i , 1 , n){
        for(auto v : tp) ct[a[i] ^ v]++;
        while(jj <= tott && c[jj].ii < i) jj++;
        while(jj <= tott && c[jj].ii == i){
            rep(j , c[jj].l , c[jj].r){
                q[c[jj].id].ans += c[jj].fg * ct[a[j]];
                if(j <= i && k == 0) q[c[jj].id].ans -= c[jj].fg;
            }
            jj++;
        }
    }
    rep(i , 1 , m) q[i].ans += q[i - 1].ans;
    vector<int>ans(m+1);
    rep(i , 1 , m) ans[q[i].id] = q[i].ans;
    rep(i , 1 , m) cout << ans[i] << '\n';
}

习题：P5047、P5398、P6778。

都是莫队二次离线的好题，值得一做。