慕容琳的后花园
慕容琳的后花园
学习笔记#莫队

引入

一道经典的莫队例题:洛谷P2709 小B的询问
小B有一个序列,包含 N1K 之间的整数。他一共有 M 个询问,每个询问给定一个区间 [L,R] ,求 \sum\limits_{i=1}^{k}c_i^2 的值,其中 c_i 表示数字 i[L,R] 中的重复次数。小B请你帮助他回答询问。

思考

方法1

想什么呢,直接暴力多好
每次从 L 扫到 R
期望得分0

方法2

设两个指针l和r,对于两个询问重新扫一遍
而是把l和r指针一格一格移动过去
但是吧,这是个假算法,如果两次询问之间l和r差的很远
效率还不如方法1

莫队

莫队是一个优美的暴力算法,普通莫队的最劣复杂度是 n \sqrt n
这已经可以应付大多数奇奇怪怪的题
怎么做呢,我们对询问区间离线处理,基于分块来排序
如果两个询问的左端点在同一块内,按右端点排
如果左端点不在同一块内,按左端点排
然后再结合方法2,发现移动指针的复杂度就是 n \sqrt n
下面给出严谨的证明:
左端点在块内一次最多移动 \sqrt n ,块内最多移动 n
块外的两个左端点最多移动 n ,块外最多移动 \sqrt n
右端点在一块内总共移动 n ,总共 \sqrt n
右端点在块外一次最多移动 n ,快外最多移动 \sqrt n
那么复杂度就是 n \sqrt n

ac代码

#include<bits/stdc++.h>
using namespace std;
int n,m,k,K,cnt[50010],a[50010],ans[50010],to[50010];
struct node
{
    int id,l,r;
    void init(int i){id=i,scanf("%d%d",&l,&r);}
    bool operator<(const node&a)const
        {return to[l]==to[a.l]?(to[l]&1?r<a.r:r>a.r):l<a.l;}
}q[50010];
int main()
{
    scanf("%d%d%d",&n,&m,&k),K=sqrt(n);
    for(int i=1;i<=n;i++)to[i]=(i-1)/K+1;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=m;i++)q[i].init(i);
    sort(q+1,q+m+1);
    int l=1,r=0,res=0;
    for(int i=1;i<=m;i++)
    {
        while(r<q[i].r)cnt[a[++r]]++,res+=2*cnt[a[r]]-1;
        while(l>q[i].l)cnt[a[--l]]++,res+=2*cnt[a[l]]-1;
        while(l<q[i].l)cnt[a[l]]--,res-=2*cnt[a[l++]]+1;
        while(r>q[i].r)cnt[a[r]]--,res-=2*cnt[a[r--]]+1;
        ans[q[i].id]=res;
    }
    for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
    return 0;
}
赞赏
https://secure.gravatar.com/avatar/8cbc0c58deea66b18e9a96cd4bdd6eea?s=256&d=monsterid&r=g

慕容琳

文章作者

发表评论

textsms
account_circle
email

慕容琳的后花园

学习笔记#莫队
引入 一道经典的莫队例题:洛谷P2709 小B的询问 小B有一个序列,包含 $ N $ 个 $ 1 $ 到 $ K $ 之间的整数。他一共有 $ M $ 个询问,每个询问给定一个区间 $ [L,R] $ ,求 $ \sum\limits…
扫描二维码继续阅读
2019-11-02
功能