莫队算法学习笔记

莫队算法

原博客地址https://www.cnblogs.com/WAMonster/p/10118934.html

题目背景

来一道题，给出一个序列，询问某一段区间中，包含多少种不同的数。

最简单的解法就是暴力，每次暴力遍历区间，这样的时间复杂度是无法接受的。

下面来做一个优化：

每次枚举到一个数值x，增加出现次数时判断一下cnt(x)是否为0，如果为0，则这个数值之前没有出现过，现在出现了，数值数要+1，反之从区间中删除x后也判断一下cnt(x)是否为0，如果为0总数-1。

然后开两个指针l和r，每次询问不直接枚举，而是移动l和r指针到询问的区间，在统计答案时只在两个指针处加减cnt，然后我们就可以用上一步的办法快速统计答案。

但是，这个优化在面对区间之间的距离相差很大的时候，即两个指针疲于奔命，从头到尾又从尾到头，这样造成时间复杂度的严重退化，这是我们不能接受的。

考虑进一步优化。

我们可以考虑把所有查询区间按左端点排序，从而使左指针最多移动O(n)次，这样右端点又是无序的，整体复杂度在面对极端数据时还是无计可施。

至此，强大的莫队算法正式开始。

预处理

莫对算法操作的核心是分块和排序，我们将大小为n的块分成根号n个块，从1到根号n编号，然后对所有查询区间排序，按左端点在块的编号排序，再按右端点在块的编号排序，排完序后左右指针就以块为单位跳来跳去，看似一顿鸡肋的操作，却优化了一个根号n的时间复杂度！

具体实现

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+100;
int a[maxn];
int cnt[maxn];
int belong[maxn];
int n,m,size,bnum,now,ans[maxn];
struct query {
    int l,r,id;
}q[maxn];
int cmp (query a,query b) {
    return (belong[a.l]^belong[b.l])?belong[a.l]<belong[b.l]:((belong[a.l]&1)?a.r<b.r:a.r>b.r);
} 
void add(int pos) {
    if(!cnt[a[pos]]) ++now;
    ++cnt[a[pos]];
}
void del(int pos) {
    --cnt[a[pos]];
    if(!cnt[a[pos]]) --now;
}
int main () {
    cin>>n;
    size=sqrt(n);
    bnum=n/size+(n%size>0);
    for (int i=1;i<=bnum;i++) 
        for (int j=(i-1)*size+1;j<=i*size;j++)
            belong[j]=i;
    for (int i=1;i<=n;i++) cin>>a[i];
    cin>>m;
    for (int i=1;i<=m;i++) {
        cin>>q[i].l>>q[i].r;
        q[i].id=i;
    }
    sort(q+1,q+m+1,cmp);
    int l=1,r=0;
    for (int i=1;i<=m;i++) {
        int ql=q[i].l;
        int qr=q[i].r;
        while (l<ql) now-=!--cnt[a[l++]];
        while (l>ql) now+=!cnt[a[--l]]++;
        while (r<qr) now+=!cnt[a[++r]]++;
        while (r>qr) now-=!--cnt[a[r--]];
        //等价于下面被注释的部分 
        /*
        while(l < ql) del(l++);
        while(l > ql) add(--l);
        while(r < qr) add(++r);
        while(r > qr) del(r--);
        */
        ans[q[i].id] = now;
    }
    for (int i=1;i<=m;i++) cout<<ans[i]<<"
"; 
}

带修改的莫队

在上一题的基础上，增加单点修改的操作。

遇到强制在线的待修改题，莫队确实无计可施。

但是对于允许离线的待修改区间查询，莫队还是可以操作的。

做法就是把莫队加上一维，变成带修改的莫队。

具体做法就是，把修改操作编号，可以理解为一个时间轴，查询操作的时间轴沿用最近修改操作的时间轴。计算时定义当前时间轴为t，对于每个查询操作，如果当前的时间轴相对太大了，说明已进行的修改操作比要求的多，就把之前改的改回来，反之往后改。只有当当前区间和查询区间的左右端点、时间轴重合时，才认定区间完全重合，此时的答案就是题目要求的答案。

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+100;
int a[maxn];
int cnt[maxn];
int ans[maxn];
int belong[maxn];
struct query {
    int l,r,t,id;
}q[maxn];
struct modify {
    int pos;
    int color;
    int lst;
}c[maxn];
int cntq,cntc,n,m,size,bnum;
int cmp (query a,query b) {
    return (belong[a.l]^belong[b.l])?belong[a.l]<belong[b.l]:((belong[a.r]^belong[b.r])?belong[a.r]<belong[b.r]:a.t<b.t);
}
int main () {
    cin>>n>>m;
    size=pow(n,2.0/3.0);//数学证明这样是最优的分块
    bnum=ceil((double)n/size);
    for (int i=1;i<=bnum;i++)
        for (int j=(i-1)*size+1;j<=i*size;j++)
            belong[j]=i;
    for (int i=1;i<=n;i++) cin>>a[i];
    for (int i=1;i<=m;i++) {
        string s;
        cin>>s;
        if (s=="Q") {
            cntq++;
            cin>>q[cntq].l>>q[cntq].r;
            q[cntq].t=cntc;
            q[cntq].id=cntq;
        }
        else {
            cntc++;
            cin>>c[cntc].pos>>c[cntc].color;
        }
    } 
    sort(q+1,q+cntq+1,cmp);
    int l=1,r=0,tt=0,now=0;
    for (int i=1;i<=cntq;i++) {
        int ql=q[i].l,qr=q[i].r,qt=q[i].t;
        while (l<ql) now-=!--cnt[a[l++]];
        while (l>ql) now+=!cnt[a[--l]]++;
        while (r<qr) now+=!cnt[a[++r]]++;
        while (r>qr) now-=!--cnt[a[r--]];
        while (tt<qt) {
            tt++;
            if (ql<=c[tt].pos&&c[tt].pos<=qr) 
                now-=!--cnt[a[c[tt].pos]]-!cnt[c[tt].color]++;
            swap(a[c[tt].pos],c[tt].color);
        }
        while (tt>qt) {
            if (ql<=c[tt].pos&&c[tt].pos<=qr) 
                now-=!--cnt[a[c[tt].pos]]-!cnt[c[tt].color]++;
            swap(a[c[tt].pos],c[tt].color);
            tt--;
        }
        ans[q[i].id]=now;
    }
    for (int i=1;i<=cntq;i++) cout<<ans[i]<<"
";
}

树上莫队

先解决一个最基本的问题，就是询问节点的子树节点数量，这其实很简单，跑一遍DFS序，记录每个节点入栈和出栈的时间，时间差就是答案。

把之前的问题放到一颗树上，给出一个n个节点的树，每个节点表示一个整数，问u到v的路径上有多少个不同的整数。

我们用一遍DFS序求出这个树的欧拉序列，然后就可以转换成序列问题。具体计算时要结合LCA，这里用倍增法求LCA。

然后到这里我懵b了。之后补。。。