莫队

libohan0905 · 2023-03-25 16:24:00 · 个人记录

前置芝士：分块

一般莫队的题有以下几个特征：

不强制在线。
可以用时间复杂度为 \mathcal{O}(n\sqrt{n}) 的算法通过。

但它也有优点：

代码相对简短。
复杂度相对较优秀。

以下一般认为 n,m 同阶，以 T 为块长。

下面引入一道题来熟悉莫队：

P2709 小B的询问

有一个长为 n 的整数序列 a，值域为 [1,k]。
一共有 m 个询问，每个询问给定一个区间 [l,r]，求： \sum\limits_{i=1}^k c_i^2
其中 c_i 表示数字 i 在 [l,r] 中的出现次数。
对于 100\% 的数据，1\le n,m,k \le 5\times 10^4。

未强制在线，这里考虑用莫队。

考虑每次遇到一个 a_i，对答案贡献为 2c_{a_i}+1（此处 c_{a_i} 指改变前的），减小同理。

我们把所有询问离线下来，按 l,r 排序。然后暴力转移指针就好了。

吗？怎么可能！时间复杂度最坏还是 \mathcal{O}(nm) 。

这里使用分块思想，对于所有左端点在同一个块里的询问，我们按它们的右端点升序排序 ，否则我们按它们的左端点升序排序。

上面这句是莫队排序的重点，然后我们考虑时间复杂度。

对于左端点移动，因为在一个块里，单次移动时间复杂度为 \mathcal{O}(T)，有 m 次询问，左端点移动的时间复杂度为：\mathcal{O}(mT)。

对于右端点移动，每个块内只往右移动，单次移动时间复杂度为 \mathcal{O}(n)，有 \dfrac{n}{T} 个块，右端点移动的时间复杂度为：\mathcal{O}(\dfrac{n^2}{T})。

那么总时间复杂度为 \mathcal{O}(mT+\dfrac{n^2}{T})，当 T 取的 \sqrt{n} 时候理论复杂度最优，为 \mathcal{O}(n\sqrt{n})。

其实可以加一个小小的优化，就是~~大名鼎鼎的~~奇偶性排序。

注意到排序只影响时间，不影响正确性，然后我们又不难发现，每一次我们处理完左端点在某一个块中的所有询问后，右端点此时应该在序列的靠右端，处理下一个块时又回到最左端了，然后又不断往右，有一些浪费。

所以我们考虑引入“奇偶块排序”，即对于左端点编号为奇数的块升序，左端点编号为偶数的块降序排序，虽然不会减少时间复杂度，但会快不少。

没加奇偶性排序的

加奇偶性排序的

#include<bits/stdc++.h>
using namespace std;
const int M = 50005;
struct node{
    int l,r,id;
}md[M];
int a[M],p[M],L,R,block;
long long Ans,ans[M];
inline bool cmp(node x,node y){
    if(x.l/block!=y.l/block) return x.l/block<y.l/block;
    if((x.l/block)&1) return x.r<y.r;
    return x.r>y.r;
}
inline void add(int id){
    Ans+=(p[a[id]]<<1|1);
    ++p[a[id]];
}
inline void del(int id){
    Ans-=((p[a[id]]<<1)-1);
    --p[a[id]];
}
long long query(int l,int r){
    while(L>l) L--,add(L);
    while(L<l) del(L),L++;
    while(R>r) del(R),R--;
    while(R<r) R++,add(R);
    return Ans;
}
int main(){
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    block=ceil(pow(n,0.5));
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        add(i);
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d",&md[i].l,&md[i].r);
        md[i].id=i;
    }
    L=1,R=n;
    sort(md+1,md+m+1,cmp);
    for(int i=1;i<=m;i++){
        ans[md[i].id]=query(md[i].l,md[i].r);
    }
    for(int i=1;i<=m;i++){
        printf("%d\n",ans[i]);
    }