【算法】莫队

一、概念

莫队是一种应用于离线询问的优美暴力算法。它是主要思想是让区间的左端点和右端点移动的距离加起来最短。

二、实现

假设现在有这样一串序列：\(1,1,4,5,1,4\)，我们现在要求询问区间内的 \(1\) 的出现次数。
如果我们现在已经统计到了区间 \((2,3)\)，现在询问 \((1,5)\)。
现在的答案是这样的：

我们发现现在的左端点 \(x=2\) 在询问的左端点的右边，所以我们将当前左端点向左移一位。现在维护的区间 \([1,3]\) 有两个 \(1\) 了。

我们又发现现在的右端点 \(y=3\) 在询问的右端点左边，所以我们将当前右端点向右移一位。现在维护的区间 \([1,4]\) 还是有两个 \(1\)。

这时候的右端点还是在询问的右端点。所以我们再将右端点向右移一位。现在维护的区间 \([1,5]\) 有三个 \(1\) 了。

这时候访问到的区间与询问的区间完全一样，我们就可以存储答案了。

这就是莫队的思想了（。你会发现这十分的像暴力，的确如此。但是为了保证时间复杂度，我们要引入分块的思想。先将 \(l\) 按照所在块的编号排序，在每个块中，再按 \(r\) 的大小排序。

这样的话我们发现在每个块中，\(r\) 最多会移 \(n\) 次，每换一次块，就可能多移 \(n\) 次。同时，每次询问 \(l\) 都可能移动 \(size\) 次。所以时间复杂度应该为 \(O(n\times num+m\times size)=O(\frac{n^2}{size}+m\times size)\)。

我们发现每换一次块，\(r\) 可能会从最右边跑到最左边，这显然不优。所以我们考虑奇偶性优化，如果第一个块的编号为偶数，那么块的编号为偶数就将 \(r\) 升序排序，为奇数就将 \(r\) 降序排序。如果第一个块的编号为奇数，那么就都反过来。

三、代码

感觉比较板的题是这题：小B的询问

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e4+5;
int n,m,k;
int a[N];
int buc[N]; 
int ansi[N];
int T;
int sum;

struct node{
    int l,r,id;
}q[N];

bool cmp(node x,node y){
    if(x.l/T==y.l/T) return x.r<y.r;
    return x.l<y.l;
}

void add(int x){
    sum-=buc[a[x]]*buc[a[x]];
    buc[a[x]]++;
    sum+=buc[a[x]]*buc[a[x]]; 
}

void del(int x){
    sum-=buc[a[x]]*buc[a[x]];
    buc[a[x]]--;
    sum+=buc[a[x]]*buc[a[x]];
}

signed main(){
    ios::sync_with_stdio(false);
    cin>>n>>m>>k;
    T=sqrt(n);
    for(int i=1;i<=n;++i) cin>>a[i];
    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 x=1,y=0;
   for(int i=1;i<=m;++i){
       int qx=q[i].l,qy=q[i].r;
       while(x>qx){
           x--;
           add(x);
       }
       while(y<qy){
           y++;
           add(y);
       }
       while(x<qx){
           del(x);
           x++;
       }
       while(y>qy){
           del(y);
           y--;
       }
       ansi[q[i].id]=sum;
    }
    for(int i=1;i<=m;++i) cout<<ansi[i]<<"\n";
    return 0;
}

四、例题

等我咕一下（