莫队学习笔记

什么都没学会。

莫队是一个离线解决区间问题的重要算法，包括普通莫队，带修莫队，树上莫队。主要应用于没有加和性质但可以由区间$[l,r-1]$的答案轻松推出区间$[l,r]$的答案的问题。是由某年国家队队长莫涛发明的。

强烈安利莫队神仙教学：大米饼的blog

普通莫队

全网都在用的例题： Z爷的袜子

很显然，一个区间$[l,r]$的答案为$ans$的话。

$$
ans={\frac{\sum_{i=1}^{M}{sum[i]\times(sum[i]-1)}}{(r-l+1)\times(r-l)}}
$$

$M$ 表示颜色个数，$sum[i]$ 表示 $[l,r]$ 中颜色 $i$ 的个数。

显而易见的是，如果我们知道区间$[l,r-1]$的答案是$ans1$，要求区间$[l,r]$的答案$ans$的话。
$$
ans=ans1-(sum[a[r]-1])^2 +sum[a[r]]^2
$$
$a[r]$表示第$r$个袜子的颜色。这个式子可以继续展开，不过这里并不需要。

这样我们就可以将$l$和$r$两个指针反复移动来得到答案。

显然这个做法效率低下，这是莫队上场了，我们将序列分块。对所有询问进行双关键字排序，如果$l$在同块，就按$r$排序，否则按$l$排序，之后一个一个询问不断移动指针求解。

时间复杂度分析：

设块的大小为$blo$，考虑最坏情况。

先看$l$，在一个块的询问中，$l$最多从前一个块最后一个询问（位于前一个块头）到本块第一个询问（位于本块块尾）再回到本块最后一个询问（位于本块块头）。这样每个点最多要移动 $3\times blo$次，一共是$3\times n\times blo$ 次 。

再看$r$，在一个块的询问中，$r$最多从前一个快最后一个询问（在$n$）到本块第一个询问（在本块块头）到本块最后一个询问（在$n$）。要移动 $2\times n$次，一共是 $\frac{2\times n^2}{blo}$ 次。

这样我们发现，莫队的最坏复杂度是 $O(3\times n\times blo+\frac{2\times n^2}{blo})$ ，就是 $O(n\times blo+\frac{n^2}{blo})$，根据均值不等式得， $ blo=\sqrt{n}$时最优。同时我们也可以发现，对于$r$的移动，如果我们让奇数块升序，偶数块降序的话，可以起到优化的作用。

普通分块板子：

由于蜜汁爆范围，我全开了long long

#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
struct node{
    ll l,r,h;
}q[50001];
ll a[50001],l,r,m;
ll bl[50001],blo,n;
ll sum[50001],num[50001],fm[50001],ans;
inline ll gcd(ll a,ll b){return !b?a:gcd(b,a%b);}
inline bool cmp(node c,node d){return bl[c.l]==bl[d.l]?c.r<d.r:c.l<d.l;}
inline void add(ll x,ll y){
    if (y<0){
        ans-=sum[a[x]]*(sum[a[x]]-1);
        ans+=(sum[a[x]]-1)*(sum[a[x]]-2);
        sum[a[x]]--;
    }
    else{
        ans-=sum[a[x]]*(sum[a[x]]-1);
        ans+=(sum[a[x]]+1)*sum[a[x]];
        sum[a[x]]++;
    }
}
int main(){
    scanf("%lld%lld",&n,&m); blo=sqrt(n);
    for (int i=1; i<=n; i++){
        scanf("%lld",&a[i]);
        bl[i]=(i-1)/blo+1;
    }
    for (int i=1; i<=m; i++){
        scanf("%lld%lld",&q[i].l,&q[i].r);
        q[i].h=i;
    }
    sort(q+1,q+m+1,cmp);
    l=q[1].l; r=l; while (r<=q[1].r) add(r,1),r++;
    r--; fm[q[1].h]=(q[1].r-l+1)*(q[1].r-l); if (!ans) fm[q[1].h]=1;
    else{ll g=gcd(ans,fm[q[1].h]);num[q[1].h]=ans/g; fm[q[1].h]/=g;}
    for (ll i=2; i<=m; i++){
        while (l<q[i].l) add(l,-1),l++;
        while (l>q[i].l) l--,add(l,1);
        while (r<q[i].r) r++,add(r,1);
        while (r>q[i].r) add(r,-1),r--;
        if (!ans){fm[q[i].h]=1;continue;}
        fm[q[i].h]=(q[i].r-q[i].l+1)*(q[i].r-q[i].l);
        ll g=gcd(ans,fm[q[i].h]);
        num[q[i].h]=ans/g; fm[q[i].h]/=g;
    }
    for (int i=1; i<=m; i++) printf("%lld/%lld\n",num[i],fm[i]);
    return 0;
}

带修莫队

带修莫队所要解决的问题就是在普通莫队的同时支持修改操作，但同样是离线，用引用时间指针的方法，将莫队原本的”平面最近点对最小生成树”变成了立体。

例题：数颜色

做法：

​ 引进时间指针$t$，表示当前操作在第几次修改操作之后，如果当前时间与询问时间不同，就进行修改或还原操作。同时，排序方式也要改变，以$l$的块为第一关键字，$r$的块为第二关键字，$t$为第三关键字排序。

时间复杂度：

​ 由于$l,r$已经分析过，现在我们只考虑$t$指针，设操作数为$m$，块的大小为$blo$，那么，$t$递增的区间最少会有$\frac{n^2}{blo^2}$个，移动数为$\frac{n^2 \times m}{blo^2}$，总复杂度$O(\frac{n^2 \times m}{blo^2}+m\times blo+\frac{n\times m}{blo})$。当$blo=n^{\frac{2}{3}}$时最小为$O(n^{\frac{5}{3}})$。

代码：

#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
struct node{
    int l,r,h,t;
}p[50001],q[50001];
int n,m,blo,l,bl[50001],a[50001],o[1000001];
int num[50001],r,t,tim,ans,que,now[50001];
inline bool cmp(node c,node d){
    if (bl[c.l]!=bl[d.l]) return c.l<d.l;
    if (bl[c.r]!=bl[d.r]) return c.r<d.r; return c.t<d.t;
}
inline void del(int x){
    o[a[x]]--; if (!o[a[x]]) ans--;
}
inline void add(int x){
    if (!o[a[x]]) ans++;o[a[x]]++;
}
inline void upd(int x,int y){
    if (l<=x&&x<=r)	del(x),a[x]=y,add(x);
    else a[x]=y;
}
int main(){
    char ch[5];
    scanf("%d%d",&n,&m); blo=pow(n,2.0/3);
    for (int i=1; i<=n; i++){
        scanf("%d",&a[i]);
        bl[i]=(i-1)/blo+1;
        now[i]=a[i];
    }
    for (int i=1; i<=m; i++){
        scanf("%s",ch);
        if (ch[0]=='Q'){
            q[++que].t=tim; q[que].h=que;
            scanf("%d%d",&q[que].l,&q[que].r);
        }
        else{
            tim++; scanf("%d%d",&p[tim].h,&p[tim].r);
            p[tim].l=now[p[tim].h]; now[p[tim].h]=p[tim].r;
        }
    }
    sort(q+1,q+que+1,cmp);
    l=0; r=0; t=0;
    for (int i=1; i<=que; i++){
        while (t<q[i].t) t++,upd(p[t].h,p[t].r);
        while (t>q[i].t) upd(p[t].h,p[t].l),t--;
        while (l<q[i].l) del(l),l++;
        while (l>q[i].l) l--,add(l);
        while (r<q[i].r) r++,add(r);
        while (r>q[i].r) del(r),r--;
        num[q[i].h]=ans;
    }
    for (int i=1; i<=que; i++) printf("%d\n",num[i]);
    return 0;
}

树上莫队

回滚莫队