学习心得 - 算法 - 莫队

· · 算法·理论

莫队

对于不好直接维护的区间问题把问题离线下来，再通过较快的单点操作完成对问题的求解。

一般是维护两个当前查询指针 l 和 r，每一次通过对 l 和 r 的变动，维护 [l,r] 信息，动态求出每一次查询的 [ql,qr] 信息。

最经典的例题就是 q 个查询区间不同数字个数。这个可以把询问排序，容易动态维护出 [l,r] 内的不同数字个数，这一点在 ABC 里经常考。

之后，我们发现这个东西还是太暴力了，一旦 update 复杂度不够优，就直接炸了。那么我们就需要在莫队上套一个分块。这样就能把左端点在同一块的放在一起，然后用分块的思想快速求出答案，复杂度可以压缩到 \mathcal O(n\sqrt{q}\times f(\tt Update))。为什么呢？我们发现令块内的右端点单调，这样一个块就最多移动 n 次，那么总共移动次数为 \frac{n^2}{\sqrt{q}}，最终 \mathcal O(mq+\sqrt{n^2}{m})，当 m=\sqrt{n^2}{q}，复杂度就是 \mathcal O(q)。

P4462 [CQOI2018] 异或序列

这题是求区间内有多少个子区间的异或值为 k，显然可以先对整个序列进行前缀和，然后求有多少对 l 和 r 满足 a_{l-1}\oplus a_{r}=k。我们考虑用莫队维护一个数出现的次数和在之前和这个值异或为 k 的个数，然后维护即可。

::::success[参考代码]

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e5+10;
int n,m,k,a[N];
ll ans[N],su;
int box[N];
int blk,bel[N];
struct qry{
    int l,r,i;
}q[N];
bool operator<(qry x,qry y){
    if(bel[x.l]!=bel[y.l])
        return bel[x.l]<bel[y.l];
    if(bel[x.l]&1)
        return x.r<y.r;
    return x.r>y.r;
}
void upd(int p){
    su+=box[a[p]^k];
    box[a[p]]++;
}
void del(int p){
    box[a[p]]--;
    su-=box[a[p]^k];
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>k;
    blk=pow(n,2/3.0);
    for(int i=1;i<=n;i++)   
        bel[i]=(i-1)/blk+1;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]^=a[i-1];
    }
    for(int i=1;i<=m;i++)
        cin>>q[i].l>>q[i].r,
        q[i].i=i;
    sort(q+1,q+m+1);
    int L=0,R=0;
    box[0]=1;
    for(int i=1;i<=m;i++){
        while(L<q[i].l-1)del(L++);
        while(L>q[i].l-1)upd(--L);
        while(R<q[i].r)upd(++R);
        while(R>q[i].r)del(R--);
        ans[q[i].i]=su;
    }
    for(int i=1;i<=m;i++)
        cout<<ans[i]<<"\n";
    return 0;
}

::::

带修/二维莫队

我们需要将除了最后一维分块，复杂度是 \mathcal O(n^\frac{5}{3})。但是复杂度容易被炸飞。而带修莫队相当于在时间维度上的变动。

::::success[参考代码]

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=3e5+10;
int n,m,a[N];
ll ans[N],su;
int box[N*10];
int blk,bel[N];
struct qry{
    int l,r,i,t;
}q[2][N];
int cur[2];
bool operator<(qry x,qry y){
    if(bel[x.l]!=bel[y.l])
        return x.l<y.l;
    if(bel[x.r]!=bel[y.r])
        return x.r<y.r;
    return x.t<y.t;
}
void upd(int p){
    su+=!box[p];
    box[p]++;
}
void del(int p){
    box[p]--;
    su-=!box[p];
}
void tim(int i,int p){
    if(q[0][i].l<=q[1][p].l&&q[1][p].l<=q[0][i].r){
        del(a[q[1][p].l]);
        upd(q[1][p].r);
    }
    swap(a[q[1][p].l],q[1][p].r);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    blk=pow(n,2/3.0);   
    for(int i=1;i<=n;i++)   
        bel[i]=i/blk;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=m;i++){
        char op;
        int l,r;
        cin>>op>>l>>r;
        if(op=='Q')
            ++cur[0],q[0][cur[0]]={l,r,cur[0],cur[1]};
        else
            q[1][++cur[1]]={l,r,0,0};
    }
    sort(q[0]+1,q[0]+cur[0]+1);
    int L=1,R=0,T=0;
    box[0]=1;
    for(int i=1;i<=cur[0];i++){
        while(L<q[0][i].l)del(a[L++]);
        while(L>q[0][i].l)upd(a[--L]);
        while(R<q[0][i].r)upd(a[++R]);
        while(R>q[0][i].r)del(a[R--]);
        while(T<q[0][i].t)tim(i,++T);
        while(T>q[0][i].t)tim(i,T--);
        ans[q[0][i].i]=su;
    }
    for(int i=1;i<=cur[0];i++)
        cout<<ans[i]<<"\n";
    return 0;
}

::::

树上莫队

维护一个 dfn 序，然后按照顺序去做莫队。