莫队 | headless-piston's Blog

引入

莫队的实现依赖于离线，将查询操作记录下来并按一定规则排序，然后使用双指针暴力求解答案，是一种优雅的暴力。
关于离线思想，可以做这一道题体验一下。~~（但是这题卡莫队）~~

例题

所以看这题的弱化版。
莫队的关键在于优化了暴力枚举的顺序，联系分块思想，将长度为 $n$ 的原序列分成长为 $\sqrt{n}$ 的块，以区间左端点所在的块的编号为第一关键字，区间右端点为第二关键字升序排序。

struct Query{
    int l,r,id;
}query[M];
bool cmp(Query x,Query y){
    return belong[x.l]==belong[y.l]?x.r<y.r:belong[x.l]<belong[y.l];
}//一定注意左端点要belong[]而右端点不用

对答案的获取，我们每次从区间 $[l,r]$ 移动到 $[l-1,r]$，$[l+1,r]$，$[l,r-1]$ 和 $[l,r+1]$。

void add(int x){
    if(!b[a[x]])
        now++;
    b[a[x]]++;
    return;
}
void del(int x){
    b[a[x]]--;
    if(!b[a[x]])
        now--;
    return;
}
//...
l=1,r=0,now=0;
for(int i=1;i<=q;i++){
    while(r<query[i].r)
        add(++r);
    while(r>query[i].r)
        del(r--);
    while(l<query[i].l)
        del(l++);
    while(l>query[i].l)
        add(--l);
    ans[query[i].id]=now;
}

易错点：一定注意自增自减符的位置，对于 add 操作应写在前面，而 delete 操作应写在后面。
注意：一定要先写右指针的移动，不然对于一些特殊的题目容易死掉。比如这道题。
时间复杂度 $O(n\sqrt n)$。每次查询左指针在块内最多移动 $O(\sqrt n)$，总体 $O(q\cdot\sqrt n)$，每个块内右指针最多移动 $O(n)$，总体 $O(n\cdot\sqrt n)$，总时间复杂度 $O(q\cdot\sqrt{n}+n\cdot\sqrt{n})$，$q$ 与 $n$ 同阶，故总时间复杂度 $O(n\sqrt n)$。

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=30010,M=200010,MAXN=1e6+10;
int n,a[N],ans[M],b[MAXN],q,belong[N],block,l,r,now;
struct Query{
    int l,r,id;
}query[M];
bool cmp(Query x,Query y){
    return belong[x.l]==belong[y.l]?x.r<y.r:belong[x.l]<belong[y.l];
}
void add(int x){
    if(!b[a[x]])
        now++;
    b[a[x]]++;
    return;
}
void del(int x){
    b[a[x]]--;
    if(!b[a[x]])
        now--;
    return;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",a+i);
    block=sqrt(n);
    for(int i=1;i<=n;i++)
        belong[i]=(i-1)/block+1;
    scanf("%d",&q);
    for(int i=1;i<=q;i++){
        scanf("%d%d",&query[i].l,&query[i].r);
        query[i].id=i;
    }
    sort(query+1,query+1+q,cmp);
    l=1,r=0,now=0;
    for(int i=1;i<=q;i++){
        while(r<query[i].r)
            add(++r);
        while(r>query[i].r)
            del(r--);
        while(l<query[i].l)
            del(l++);
        while(l>query[i].l)
            add(--l);
        ans[query[i].id]=now;
    }
    for(int i=1;i<=q;i++)
        printf("%d\n",ans[i]);
    return 0;
}

优化

奇偶排序优化。
与普通莫队排序区别是：对于左端点在一个块内的时候，若在奇块内，则右端点升序排序，反之则降序排序。

bool cmp(Query x,Query y){
    if(belong[x.l]!=belong[y.l])
        return belong[x.l]<belong[y.l];
    return (belong[x.l]&1)?(x.r<y.r):(x.r>y.r);
}

理论大约能减少 $30\%$ 的指针移动次数。
我们考虑奇块因为右端点升序，到达块末尾时右指针应当较为靠后，而偶数块是降序，起始右指针也较为靠后，偶块转奇块同理，体现了一种“自然衔接”。
可以看看模板题：[国家集训队] 小 Z 的袜子
设区间 $[l,r]$ 中某颜色袜子数为 $x_i$，则选出两只这种袜子的概率为

$\frac{x_i}{r-l+1}\cdot \frac{x_i-1}{r-l}$

则对于所有 $i$，总的概率为

$\frac{\sum x_i^2+\sum x_i}{(r-l+1)(r-l)}$

$\sum x_i$ 和 $\sum x_i^2$ 都可以用脚维护。

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
template<typename T>
inline void read(T &x){
    bool f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    if(f) x=~x+1;
}
template<typename T,typename...Args>
void read(T &x,Args &...args){read(x);read(args...);}
typedef long long ll;
constexpr int N=50010;
int n,m,c[N],belong[N],block,sum,cnt[N];
ll sum2;
struct query{
    int l,r,id;
    bool operator<(const query &x)const{
        if(belong[l]^belong[x.l])
            return belong[l]<belong[x.l];
        return belong[l]&1?r<x.r:r>x.r;
    }
}q[N];
struct Ans{
    ll a,b;
    Ans(){}
    Ans(ll a,ll b):a(a),b(b){}
}ans[N];
inline void add(int x){
    sum2-=(ll)cnt[x]*cnt[x];
    ++cnt[x],++sum;
    sum2+=(ll)cnt[x]*cnt[x];
}
inline void del(int x){
    sum2-=(ll)cnt[x]*cnt[x];
    --cnt[x],--sum;
    sum2+=(ll)cnt[x]*cnt[x];
}
int main(){
    read(n,m);
    block=sqrt(n);
    for(int i=1;i<=n;i++) belong[i]=(i-1)/block+1;
    for(int i=1;i<=n;i++) read(c[i]);
    for(int i=1;i<=m;i++){
        read(q[i].l,q[i].r);
        q[i].id=i;
    }
    sort(q+1,q+1+m);
    int l=1,r=0;
    for(int i=1;i<=m;i++){
        if(q[i].l==q[i].r){
            ans[q[i].id]=Ans(0,1);
            continue;
        }
        while(r<q[i].r) add(c[++r]);
        while(r>q[i].r) del(c[r--]);
        while(l<q[i].l) del(c[l++]);
        while(l>q[i].l) add(c[--l]);
        ll a=sum2-sum,b=(r-l+1ll)*(r-l),c=__gcd(a,b);
        ans[q[i].id]=Ans(a/c,b/c);
    }
    for(int i=1;i<=m;i++)
        printf("%lld/%lld\n",ans[i].a,ans[i].b);
    return 0;
}

带修莫队

考虑把修改操作和查询操作同时记录下来，把每个查询操作额外记录距离当次查询最近的一次修改的位置，同时跑莫队时记录当前已经进行了几次修改，这样回答查询时可以顺次进行修改或“时光倒流”回退修改。
排序方式：
以左端点所在块的编号为第一关键字，右端点所在块的编号为第二关键字，当前操作的时间戳为第三关键字排序。注意：这里的第二关键字是右端点所在块的编号。
经证明，块长取 $n^{\frac{2}{3}}$ 较优。总体时间复杂度 $O(n^{\frac{5}{3}})$。
模板题。

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
constexpr int N=133353,M=1e6+10;
char op;
int n,m,tot,block,belong[N],qcnt,mcnt,b[M],sum,a[N],ans[N];
struct query{
    int l,r,t,id;
    query(int l=0,int r=0,int t=0,int id=0):l(l),r(r),t(t),id(id){}
    inline bool operator<(const query &x)const{
        if(belong[l]^belong[x.l]) return belong[l]<belong[x.l];
        if(belong[r]^belong[x.r]) return belong[r]<belong[x.r];
        return t<x.t;
    }
}q[N];
struct modify{
    int x,k;
    modify(int x=0,int k=0):x(x),k(k){}
}mo[N];
inline void add(const int &x){if(0==b[x]++) ++sum;}
inline void del(const int &x){if(0==--b[x]) --sum;}
inline void update(const int &x,const int &t){
    if(q[x].l<=mo[t].x&&q[x].r>=mo[t].x){
        del(a[mo[t].x]);
        add(mo[t].k);
    }
    std::swap(a[mo[t].x],mo[t].k);
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    block=pow(n,2.0/3);
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) belong[i]=(i-1)/block+1;
    for(int i=1,x,y;i<=m;i++){
        cin>>op>>x>>y;
        if(op^'R') ++qcnt,q[qcnt]=query(x,y,mcnt,qcnt);
        else mo[++mcnt]=modify(x,y);
    }
    std::sort(q+1,q+1+qcnt);
    for(int i=1,l=1,r=0,t=0;i<=qcnt;i++){
        while(l>q[i].l) add(a[--l]);
        while(r<q[i].r) add(a[++r]);
        while(l<q[i].l) del(a[l++]);
        while(r>q[i].r) del(a[r--]);
        while(t<q[i].t) update(i,++t);
        while(t>q[i].t) update(i,t--);
        ans[q[i].id]=sum;
    }
    for(int i=1;i<=qcnt;i++) cout<<ans[i]<<'\n';
    return 0;
}