【学习笔记】莫队二次离线、另一种值域分块

· · 算法·理论

0.前言

问一下，花了三天左右的时间研究了一下莫队二次离线，这时间花得值得吗？

咕了好久，一直说要写的，过了半年终于写完了。

前情提要：【学习笔记】值域分块、根号平衡和莫队。

本篇学习笔记主要讲解莫队二次离线与另一种值域分块，本文默认读者拥有足够的数据结构基础。

给 lxl 跪了。

1.正文

莫队二次离线

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

传送门

先来看一道模板题。

我们认为 n 和 m 同阶，且显然 k>14 时所有询问的答案都为 0。

我们先处理出来所有 \operatorname{popcount}(x)=k 的 x 并存起来。

朴素莫队需要动态维护一个桶，利用异或的性质，每次遍历所有 \operatorname{popcount} 为 k 的数，更新对应位置的答案。

单次移动指针的复杂度为 O\left(\binom{14}{k}\right)，单次查询的复杂度为 O(1)，总时间复杂度为 O\left(\binom{14}{k} n\sqrt n+n\right)。

你发现这个时间复杂度非常爆炸。

考虑普通莫队中，移动指针时对答案的更新过程，即一个数，与一个区间相互贡献，对答案的变化量。

我们设这个贡献为 f(x,[l,r])。

那么以右端点向右扩展为例，从 [l,r] 扩展到 [l,r']，答案的变化量为：

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

我们进行一个差分：

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

拆成两部分：

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

我们发现前面的和式与每次扩展的区间无关，可以预处理出来。

而后面的和式不好处理，我们就再把后面这些询问存下来，再次离线处理。

那么，怎么存呢？

我们观察到，后面的函数有一个特点，那就是我们计算的是一个点（或一个区间）到一个前缀的贡献。

我们把询问参数 r+1、r' 和对应的系数 1 或 -1 挂在前缀 l-1 的位置，对前缀扫描线，计算所有挂在当前前缀上的答案。

扫描线单次加入一个数的复杂度为 O\left(\binom{14}{k}\right)，单次询问一个数对当前桶的答案复杂度为 O(1)，总复杂度 O\left(\binom{14}{k}n+n\sqrt n\right)。

我们发现，经过二次离线处理后，我们把单次移动指针 n\sqrt n 上乘的 \binom{14}{k} 给挪到了 n 上。

对于当前的区间 [l,r] 的扩展，我们分四种情况统计答案的变化量：

\begin{aligned} \Delta \mathrm{Ans}&=\sum_{i=r+1}^{r'}f(i,[l,i-1]) \\ &= \sum_{i=r+1}^{r'}f(i,[1,i-1]) - \sum_{i=r+1}^{r'}f(i,[1,l-1]) \end{aligned} \begin{aligned} \Delta \mathrm{Ans}&=\sum_{i=l'}^{l-1}f(i,[i+1,r]) \\ &= - \sum_{i=l'}^{l-1}f(i,[1,i]) + \sum_{i=l'}^{l-1}f(i,[1,r]) \end{aligned} \begin{aligned} -\Delta \mathrm{Ans}&=\sum_{i=r'+1}^{r}f(i,[l,i-1]) \\ &= \sum_{i=r'+1}^{r}f(i,[1,i-1]) - \sum_{i=r'+1}^{r}f(i,[1,l-1]) \end{aligned} \begin{aligned} -\Delta \mathrm{Ans}&=\sum_{i=l}^{l'-1}f(i,[i+1,r]) \\ &= -\sum_{i=l}^{l'-1}f(i,[1,i]) + \sum_{i=l}^{l'-1}f(i,[1,r]) \end{aligned}

对于指针的移动，分情况处理好细节就可以了。

实现

让我们一步一步研究莫队二次离线的实现细节。

预处理

for(int i=0;i<16384;i++) if(__builtin_popcount(i)==k) bts.push_back(i);
for(int i=1;i<=n;i++){
    pre[i][0]=bkt[a[i]]+pre[i-1][0];
    for(int x:bts) bkt[a[i]^x]++;
    pre[i][1]=bkt[a[i]]+pre[i-1][1];
}
memset(bkt,0,sizeof bkt);

首先处理出来哪些数会对答案有贡献，即 \operatorname{popcount}(x)=k 的所有 x。

pre[t][0] 表示 \sum_{i=1}^{t}f(i,[1,i-1])。

pre[t][1] 表示 \sum_{i=1}^{t}f(i,[1,i])。

模拟普通莫队的过程

int nowl=1,nowr=0;
for(int p=1;p<=m;p++){
    int pl=q[p].l,pr=q[p].r;

    if(nowr<pr){
        Ans[p]+=pre[pr][0]-pre[nowr][0];
        vec[nowl-1].push_back({nowr+1,pr,p,-1});
        nowr=pr;
    }
    if(pl<nowl){
        Ans[p]-=pre[nowl-1][1]-pre[pl-1][1];
        vec[nowr].push_back({pl,nowl-1,p,1});
        nowl=pl;
    }
    if(pr<nowr){
        Ans[p]-=pre[nowr][0]-pre[pr][0];
        vec[nowl-1].push_back({pr+1,nowr,p,1});
        nowr=pr;
    }
    if(nowl<pl){
        Ans[p]+=pre[pl-1][1]-pre[nowl-1][1];
        vec[nowr].push_back({nowl,pl-1,p,-1});
        nowl=pl;
    }
}

这段代码模拟普通莫队的处理过程，并把需要二次离线计算的内容保存下来。

这里的所有坐标及系数 1 和 -1 都来自上面的分析。

但是我们注意到一件事：Ans[p]+=pre[pr][0]-pre[nowr][0] 和 Ans[p]-=pre[nowr][0]-pre[pr][0] 是本质相同的。

所以我们可以稍微压缩一下这段特别长的代码：

int nowl=1,nowr=0;
for(int p=1;p<=m;p++){
    int pl=q[p].l,pr=q[p].r;

    Ans[p]+=pre[pr][0]-pre[nowr][0];
    Ans[p]+=pre[pl-1][1]-pre[nowl-1][1];
    if(nowr<pr) vec[nowl-1].push_back({nowr+1,pr,p,-1}),nowr=pr;
    if(pl<nowl) vec[nowr].push_back({pl,nowl-1,p,1}),nowl=pl;
    if(pr<nowr) vec[nowl-1].push_back({pr+1,nowr,p,1}),nowr=pr;
    if(nowl<pl) vec[nowr].push_back({nowl,pl-1,p,-1}),nowl=pl;
}

顺手压一下行。

计算二次离线

for(int i=1;i<=n;i++){
    for(int x:bts) bkt[a[i]^x]++;
    for(auto [l,r,id,v]:vec[i]) for(int k=l;k<=r;k++) Ans[id]+=bkt[a[k]]*v;
}

这部分反而不是很难，本质只是一个简单的扫描线。

完整代码

需要注意的是最后计算出的答案数组是差分数组，需要进行一次前缀和，并重新排序才能输出正确答案。

:::info[Code]

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3fll
using namespace std;

int n,m,k;
int a[100010];

int block_length;
int belong[100010];

struct queries{
    int l,r,id,v;
}q[100010];

vector<int> bts;

int bkt[1048576];
long long pre[100010][2];
vector<queries> vec[100010];

long long Ans[100010],tmpAns[100010];

int main(){
    cin.tie(0)->sync_with_stdio(false);

    cin>>n>>m>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++) cin>>q[i].l>>q[i].r,q[i].id=i;

    if(k>14){
        for(int i=1;i<=m;i++) cout<<"0\n";
        return 0;
    }

    block_length=sqrt(n);
    for(int i=1;i<=n;i++) belong[i]=(i-1)/block_length+1;
    sort(q+1,q+1+m,[&](queries x,queries y){
        if(belong[x.l]!=belong[y.l]) return belong[x.l]<belong[y.l];
        else if(belong[x.l]&1) return x.r<y.r;
        else return x.r>y.r;
    });

    for(int i=0;i<16384;i++) if(__builtin_popcount(i)==k) bts.push_back(i);
    for(int i=1;i<=n;i++){
        pre[i][0]=bkt[a[i]]+pre[i-1][0];
        for(int x:bts) bkt[a[i]^x]++;
        pre[i][1]=bkt[a[i]]+pre[i-1][1];
    }
    memset(bkt,0,sizeof bkt);

    int nowl=1,nowr=0;
    for(int p=1;p<=m;p++){
        int pl=q[p].l,pr=q[p].r;

        Ans[p]+=pre[pr][0]-pre[nowr][0];
        Ans[p]+=pre[pl-1][1]-pre[nowl-1][1];
        if(nowr<pr) vec[nowl-1].push_back({nowr+1,pr,p,-1}),nowr=pr;
        if(pl<nowl) vec[nowr].push_back({pl,nowl-1,p,1}),nowl=pl;
        if(pr<nowr) vec[nowl-1].push_back({pr+1,nowr,p,1}),nowr=pr;
        if(nowl<pl) vec[nowr].push_back({nowl,pl-1,p,-1}),nowl=pl;
    }

    for(int i=1;i<=n;i++){
        for(int x:bts) bkt[a[i]^x]++;
        for(auto [l,r,id,v]:vec[i]) for(int k=l;k<=r;k++) Ans[id]+=bkt[a[k]]*v;
    }

    for(int i=1;i<=m;i++) Ans[i]+=Ans[i-1];
    for(int i=1;i<=m;i++) tmpAns[q[i].id]=Ans[i];
    for(int i=1;i<=m;i++) cout<<tmpAns[i]<<"\n";

    # ifdef TakanashiHoshino
    cerr<<"\nUsed time: "<<clock()*1.0/CLOCKS_PER_SEC<<"s.\n";
    # endif
    return 0;
}

:::

常见问题

因为二次离线莫队与普通莫队的差别只是把单次转移拆开计算。自然需要先保证普通莫队的复杂度，才能保证二次离线莫队的复杂度。

有的题中，一个数不会对自己有贡献；而有的题不一定。这时需要分清一个数对自己是否存在贡献，本文的写法是一个不用动脑子的写法。

值域分块

相比于 O(1) 插入删除一个数，O(\sqrt n) 查询的值域分块，有些时候 O(\sqrt n) 插入删除，O(1) 查询的值域分块也能做到根号平衡。

原理与上一篇博客类似，此处仅作简略介绍。

维护的信息：

换句话说，\mathrm{cnt} 和 \mathrm{blockcnt} 维护的分别是块内的前缀和和整块间的前缀和。

\operatorname{insert}/\operatorname{erase}

向集合中插入 / 删除一个数 x。

由于我们维护的是前缀和，所以我们需要修改 \mathrm{cnt} 和 \mathrm{blockcnt} 的整个后缀，数量级是 O(B+\frac{n}{B}) 的。

时间复杂度 O(B+\frac{n}{B})。

void insert(int x){
    for(int i=x;i<block_begin[belong[x]+1];i++) cnt[i]++;
    for(int i=belong[x];i<=belong[n];i++) blockcnt[i]++;
}

void erase(int x){
    for(int i=x;i<block_begin[belong[x]+1];i++) cnt[i]--;
    for(int i=belong[x];i<=belong[n];i++) blockcnt[i]--;
}

\operatorname{query}/\operatorname{getrank}

查询小于等于 x 的数的数量 / 小于 x 的数的数量加一。

可以直接使用 \mathrm{cnt} 和 \mathrm{blockcnt} 在 O(1) 时间内计算，与块长 B 无关。

\operatorname{query}(x)=\mathrm{blockcnt}_{\mathrm{belong}_x-1}+\mathrm{cnt}_x \\ \operatorname{getrank}(x)=\operatorname{query}(x-1)+1 
int query(int x){
    return blockcnt[belong[x]-1]+cnt[x];
}

int getrank(int x){
    return query(x-1)+1;
}

\operatorname{getkth}

求出排名为 x 的数是多少。

因为这个东西等价于“最后一个拥有 <x 个小于它的数”，所以一种方法是遍历一遍整块，然后到达阈值之后遍历散块获取答案，时间复杂度 O(B+\frac{n}{B})。

另一种方法就是你可以直接二分这个数，因为 \operatorname{getrank} 的复杂度是 O(1)，所以你二分求的时间复杂度就是 O(\log n)。

int getkth(int x){
    int l=1,r=n;
    while(l<r){
        int mid=(l+r+1)>>1;
        if(getrank(mid)-1<x) l=mid;
        else r=mid-1;
    }
    return l;
}

\operatorname{getpre}

求 x 的前驱，即小于 x，且最大的数。

我们可以先利用 \operatorname{getrank}(x) 求出 x 的排名 \mathrm{rank}。

直接考虑本质，\mathrm{rank} 代表有 \mathrm{rank}-1 个数是小于 x 的，那么小于 x 的最大的数自然就是排名为 \mathrm{rank}-1 的数。

那么有 \operatorname{getpre}(x)=\operatorname{getkth}(\operatorname{getrank}(x)-1)。

这两个函数的复杂度一个是 O(\log n) 一个是 O(1)，所以这个查询的时间复杂度为 O(\log n)。

int getpre(int x){
    return getkth(getrank(x)-1);
}

\operatorname{getnxt}

求 x 的后继，即大于 x，且最小的数。

类比 \operatorname{getpre}，要求大于 x 的数，需要先知道小于等于 x 的数有多少个。

记 \mathrm{rank}=\operatorname{getrank}(x+1)，代表有 \mathrm{rank}-1 个数小于 x+1，也就是小于等于 x。那么第一个大于 x 的数自然就是排名为 \mathrm{rank} 的数，即 \operatorname{getkth}(\mathrm{rank})。

那么有 \operatorname{getnxt}(x)=\operatorname{getkth}(\operatorname{getrank}(x+1))。

时间复杂度同为 O(\log n)。

int getnxt(int x){
    return getkth(getrank(x+1));
}

杂项

对于前驱与后继不存在的情况，一个建议的处理方式是提前向集合里插入 \infin 和 -\infin，可以避免答案不存在导致的可能的问题。

这种值域分块建议在查询时特判掉 0 的情况，否则可能会因为神秘原因访问到 blockcnt[-1] 导致爆炸。

至于复杂度，显然应该取 B=\sqrt n。

P3369 【模板】普通平衡树

传送门

没错，还是普通平衡树。

这里就直接给出参考实现了。

:::info[Code]

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3fll
using namespace std;

int n,m;

int block_length;
int belong[100010],block_begin[320];
int cnt[100010],blockcnt[320];

void insert(int x){
    for(int i=x;i<block_begin[belong[x]+1];i++) cnt[i]++;
    for(int i=belong[x];i<=belong[n];i++) blockcnt[i]++;
}

void erase(int x){
    for(int i=x;i<block_begin[belong[x]+1];i++) cnt[i]--;
    for(int i=belong[x];i<=belong[n];i++) blockcnt[i]--;
}

int query(int x){
    return blockcnt[belong[x]-1]+cnt[x];
}

int getrank(int x){
    return query(x-1)+1;
}

int getkth(int x){
    int l=1,r=n;
    while(l<r){
        int mid=(l+r+1)>>1;
        if(getrank(mid)-1<x) l=mid;
        else r=mid-1;
    }
    return l;
}

int getpre(int x){
    return getkth(getrank(x)-1);
}

int getnxt(int x){
    return getkth(getrank(x+1));
}

struct queries{
    int opt,x;
}q[100010];

namespace lsh{
    vector<int> v;
    void insert(int x){v.push_back(x);}
    void init(){sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());}
    int getid(int x){return lower_bound(v.begin(),v.end(),x)-v.begin()+1;}
    int getori(int x){return v[x-1];}
}

int main(){
    cin.tie(0)->sync_with_stdio(false);

    cin>>m;
    for(int i=1;i<=m;i++) cin>>q[i].opt>>q[i].x;

    lsh::insert(-inf),lsh::insert(inf);
    for(int i=1;i<=m;i++) if(q[i].opt!=4) lsh::insert(q[i].x);
    lsh::init();
    for(int i=1;i<=m;i++) if(q[i].opt!=4) q[i].x=lsh::getid(q[i].x);
    n=(int)lsh::v.size();

    block_length=(int)sqrt(n);
    for(int i=n;i>=1;i--) belong[i]=(i-1)/block_length+1,block_begin[belong[i]]=i;
    block_begin[belong[n]+1]=n+1;

    for(int p=1;p<=m;p++){
        int op=q[p].opt;
        if(op==1) insert(q[p].x);
        else if(op==2) erase(q[p].x);
        else if(op==3) cout<<getrank(q[p].x)<<"\n";
        else if(op==4) cout<<lsh::getori(getkth(q[p].x))<<"\n";
        else if(op==5) cout<<lsh::getori(getpre(q[p].x))<<"\n";
        else if(op==6) cout<<lsh::getori(getnxt(q[p].x))<<"\n";
    }

    # ifdef TakanashiHoshino
    cerr<<"\nUsed time: "<<clock()*1.0/CLOCKS_PER_SEC<<"s.\n";
    # endif
    return 0;
}

:::

合起来试试

讲了这么多，这俩东西之间有什么关系吗？能不能像普通莫队那样根号平衡？

P5501 [LnOI2019] 来者不拒，去者不追

传送门

稍微拆拆贡献，可以得到一个数 x 与一个区间 [l,r] 贡献时，答案的变化量为：

\pm \Delta \mathrm{Ans} = {\color{red}x + } \sum_{i=l}^{r} [a_i>x]a_i + x\sum_{i=l}^{r} [a_i<x]

那个标红的 x 的贡献是没办法一起计算的，所以我们把这个玩意单独拉出来最后再算。

此时我们发现，我们有 O(n\sqrt n) 次操作，在每次操作间都需要计算答案的变化量，也就是有 O(n\sqrt n) 次插入删除和查询操作。

但是，你注意到这个东西平衡不了。

然而你又发现这个贡献可以拆成差分形式。

变化量贡献可差分？考虑二次离线。

二次离线以后，发现在扫描线时，我们只有 O(n) 次插入操作，而有 O(n\sqrt n) 次查询操作。

诶？这个是不是能平衡一下？

用上本文的 O(\sqrt n) 插入删除、O(1) 查询的值域分块，这个代码的复杂度被成功平衡到了 O(n\sqrt n)。

二次离线莫队相比普通莫队，其查询和修改次数恰好反了过来，这给了本文维护前缀和的值域分块大展身手的机会。

:::info[参考代码]

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3fll
using namespace std;

namespace ds{
    int n;
    int block_length;
    int belong[100010],block_begin[320];

    int cnt[100010],block_cnt[320];
    long long sum[100010],block_sum[320];

    void clear(int _n){
        n=_n;
        block_length=sqrt(n);
        for(int i=1;i<=n;i++) belong[i]=(i-1)/block_length+1;
        for(int i=n;i>=1;i--) block_begin[belong[i]]=i;
        block_begin[belong[n]+1]=n+1;

        for(int i=1;i<=n;i++) cnt[i]=0,sum[i]=0;
        for(int i=1;i<=belong[n];i++) block_cnt[i]=0,block_sum[i]=0;
    }

    void insert(int x){
        for(int i=x;i<block_begin[belong[x]+1];i++) cnt[i]++,sum[i]+=x;
        for(int i=belong[x];i<=belong[n];i++) block_cnt[i]++,block_sum[i]+=x;
    }

    int query_cnt(int x){return !x?0:block_cnt[belong[x]-1]+cnt[x];}
    long long query_sum(int x){return !x?0:block_sum[belong[x]-1]+sum[x];}

    int query_cnt(int l,int r){return query_cnt(r)-query_cnt(l-1);}
    long long query_sum(int l,int r){return query_sum(r)-query_sum(l-1);}
}

int n,m,V;
int a[500010];
long long presum[500010];

struct node_query{
    int l,r,id,fac;
}q[500010];

int block_length;
int belong[500010];

long long pre[500010][2];
long long Ans[500010],tmpAns[500010];

vector<node_query> vec[500010];

int main(){
    cin.tie(0)->sync_with_stdio(false);

    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i],V=max(V,a[i]),presum[i]=presum[i-1]+a[i];
    for(int i=1;i<=m;i++) cin>>q[i].l>>q[i].r,q[i].id=i;

    block_length=sqrt(n);
    for(int i=1;i<=n;i++) belong[i]=(i-1)/block_length+1;

    sort(q+1,q+1+m,[&](node_query x,node_query y){
        if(belong[x.l]!=belong[y.l]) return belong[x.l]<belong[y.l];
        if(belong[x.l]&1) return x.r<y.r;
        else return x.r>y.r;
    });

    ds::clear(V);
    for(int i=1;i<=n;i++){
        pre[i][0]=ds::query_sum(a[i]+1,V)+1ll*a[i]*ds::query_cnt(1,a[i]-1)+pre[i-1][0];
        ds::insert(a[i]);
        pre[i][1]=ds::query_sum(a[i]+1,V)+1ll*a[i]*ds::query_cnt(1,a[i]-1)+pre[i-1][1];
    }

    int nowl=1,nowr=0;
    for(int p=1;p<=m;p++){
        int pl=q[p].l,pr=q[p].r;

        Ans[p]+=pre[pr][0]-pre[nowr][0];
        Ans[p]+=pre[pl-1][1]-pre[nowl-1][1];
        if(nowr<pr) vec[nowl-1].push_back({nowr+1,pr,p,-1}),nowr=pr;
        if(pl<nowl) vec[nowr].push_back({pl,nowl-1,p,1}),nowl=pl;
        if(pr<nowr) vec[nowl-1].push_back({pr+1,nowr,p,1}),nowr=pr;
        if(nowl<pl) vec[nowr].push_back({nowl,pl-1,p,-1}),nowl=pl;
    }

    ds::clear(V);
    for(int i=1;i<=n;i++){
        ds::insert(a[i]);
        for(auto [l,r,id,fac]:vec[i]) for(int k=l;k<=r;k++) Ans[id]+=(ds::query_sum(a[k]+1,V)+1ll*a[k]*ds::query_cnt(1,a[k]-1))*fac;
    }

    for(int i=1;i<=m;i++) Ans[i]+=Ans[i-1];
    for(int i=1;i<=m;i++) tmpAns[q[i].id]=Ans[i]+presum[q[i].r]-presum[q[i].l-1];
    for(int i=1;i<=m;i++) cout<<tmpAns[i]<<"\n";

    # ifdef TakanashiHoshino
    cerr<<"\nUsed time: "<<clock()*1.0/CLOCKS_PER_SEC<<"s.\n";
    # endif
    return 0;
}

:::

2.练习

P5398 [Ynoi2018] GOSICK

需要在二次离线的基础上根号分治。

这道题可能会硬控你很久，一定要梳理好每一种可能的贡献会在哪里计算，不要算重，不要算漏。

P5047 [Ynoi2019 模拟赛] Yuno loves sqrt technology II

非常经典的题。

需要注意，逆序对这个信息向左向右扩展时需要的信息不对称，所以我们需要把前缀信息和二次离线的询问分成两种：比 a_i 大的数的数量、比 a_i 小的数的数量。

比较自然的，我们同样会用上本文提到的值域分块。

一个性质是，一个数不可能对自己有逆序对的贡献，所以这道题中我们不需要区分前缀答案是否包含自身。

P15839 [蓝桥杯第一届国际赛] 莲蓬池

拆贡献，对两侧的信息分别统计。

3.后记

感觉这东西没什么用啊。而且除了线性空间有优势是不是几乎已经被 lxl 宣告死亡了。

算是回收了半年前的博客挖的坑了吧。

祝各位顺利进队，在赛场上得到满意的成绩。

顺手推一下本人省选游记。

青蛙。