学习笔记#分块#莫队
引入
一道经典的莫队例题：洛谷P2709 小B的询问
小B有一个序列，包含 $ N $ 个 $ 1 $ 到 $ K $ 之间的整数。他一共有 $ 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;
}
版权声明：本文为muronglin原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。