【模板】莫队算法

· · 个人记录

引入

如果你已知一个序列，你已知其 [2,6] 的区间和以及原序列，现在要你求[2,7]的区间和，你会怎么办？

显然我们可以在 [2,6] 的基础上加上原序列的第 7 位，就得到了 [2,7] 的区间和。

同理，如果我们需要求出 [2,5] 的区间和，我们只需要在 [2,6] 的基础上减去原序列的第 5 位即可。

很好理解对吧，莫队的思想就是这样，每次这样一位一位的扩展。

优化

莫队可以用于解决一些区间问题。由于含有多次询问，莫队得以展现其优势。

但是对于一种类型的情况:

查询区间[1,1] [n,n] [1,1] [n,m]...

此时我们每次询问直接处理了整个序列，复杂度直接起飞O(nm)

所以我们对询问进行离线，并对询问的左端点分块，然后按照左端点所在块为第一关键字，右端点为第二关键字的规则进行排序，复杂度大幅降低。

格式:

bool cmp(ques x,ques y){
    return x.pos==y.pos?x.r<y.r:x.pos<y.pos;
}

格式：

    int siz=sqrt(n);
    for(int i=1;i<=m;++i){
        scanf("%d%d",&q[i].l,&q[i].r);
        q[i].id=i;q[i].pos=q[i].l/siz;
    }
    sort(q+1,q+1+m,cmp);
    l=1;r=0;
    for(int i=1;i<=m;++i){
        int L=q[i].l,R=q[i].r,K=q[i].id;
        while(l<L) Sub(l++);
        while(R<r) Sub(r--);
        while(L<l) Add(--l);
        while(r<R) Add(++r);
        ans[K]=res; 
    }
    for(int i=1;i<=m;++i){
        printf("%lld\n",ans[i]);
    }

一道例题P1494 国家集训队小Z的袜子

我们只需要考虑 Add 和 Sub 函数怎么写就好啦

这个题很简单，注意细节就好啦

#include<bits/stdc++.h>
using namespace std;
#define file(a) freopen(#a".in","r",stdin),freopen(#a".out","w",stdout)
#define LL long long
#define N 50010
int n,m;
int col[N];
LL uans[N],dans[N];
struct ques{
    int l,r,id;
    int pos;
}q[N];
int l,r;
int tim[N];
LL ups,downs;
void Add(int p){
    //printf("  +%d %d %d\n",p,col[p],tim[col[p]]);
    ups+=2*tim[col[p]];
    ++tim[col[p]];
}
void Sub(int p){
    //printf("  -%d %d %d\n",p,col[p],tim[col[p]]);
    --tim[col[p]];
    ups-=2*tim[col[p]];
}
LL gcd(LL x,LL y){
    if(y==0) return x;
    return gcd(y,x%y);
}
bool cmp(ques x,ques y){
    return x.pos==y.pos?x.r<y.r:x.pos<y.pos;
}
int main(){
    //file(a);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d",&col[i]);
    }
    int siz=sqrt(n);
    for(int i=1;i<=m;++i){
        scanf("%d%d",&q[i].l,&q[i].r);
        q[i].id=i;q[i].pos=q[i].l/siz;
    }
    sort(q+1,q+1+m,cmp);
    l=1;r=0;
    for(int i=1;i<=m;++i){
        //printf("%d %d:\n",q[i].l,q[i].r);
        int L=q[i].l,R=q[i].r,K=q[i].id;
        if(L==R){
            uans[K]=0,dans[K]=1; 
            continue;
        }
        downs=1ll*(R-L+1)*(R-L);
        while(l<L) Sub(l++);
        while(R<r) Sub(r--);
        while(L<l) Add(--l);
        while(r<R) Add(++r);
        uans[K]=ups;dans[K]=downs; 
    }
    for(int i=1;i<=m;++i){
        LL Gcd=gcd(uans[i],dans[i]);
        printf("%lld/%lld\n",uans[i]/Gcd,dans[i]/Gcd);
    }
    return 0;
}