莫队算法学习笔记

莫队算法是一种利用分块思想,来解决离线区间询问问题的算法。

Part 1 普通莫队

莫队的基本思想是利用上一个询问的信息,通过移动区间头尾指针,暴力转移到下一个询问区间。

先举个例子:

[洛谷 2709]小B的询问

给出一个长度为 \(n\) 的序列,序列中所有数字均不超过一个给定的数字 \(k\),现在给出 \(m\) 次询问,每次询问区间 \([l,r]\) 中所有数字出现次数的平方和。

数据范围:\(n,m,k \leq 50000\)

最暴力的方法当然是对每个询问分别暴力扫描计算,复杂度是 \(O(nm)\) 的。

我们注意到我们可以利用上一次询问区间的信息来进行优化。具体地说,对于一个状态 \([l,r]\),我们可以通过移动区间首尾指针的方式,转移到 \([l-1,r],[l+1,r],[l,r-1],[l,r+1]\) 这样几个区间。

于是我们有了一个优化的算法:从第一个询问区间开始,每次通过暴力移动区间首尾指针的方式来更新信息,并转移到下一个询问区间。

我们可能有很多指针移动操作,所以这样还是很慢。

如果题目并不要求强制在线,我们可以将所有询问一次性读入,并通过排序的方法来使得指针的移动次数最少。

怎么排序呢?如果直接按照 \(l\) 为第一关键字,\(r\) 为第二关键字排序,虽然左端点指针移动次数少了,但右端点可能会产生大量移动。

我们来考虑分块的思想:具体来说,我们将区间分成若干块,先按照左端点所在块的编号进行排序,如果有若干区间左端点处在同一块中,则按右端点所在块的编号排序。

如果块大小取 \(\sqrt n\),可以证明这样算法的复杂度是 \(n \sqrt n\) 的。

#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
struct query
{
 int l,r,bl,br,id;
}q[50005];
long long a[50005],ans[50005],t[50005],res;
bool cmp(const query&a,const query&b)
{
 return a.bl<b.bl||(a.bl==b.bl&&a.br<b.br);
}
void del(int x)
{
 res-=2*t[a[x]]-1;
 t[a[x]]--;
}
void add(int x)
{
 res+=2*t[a[x]]+1;
 t[a[x]]++;
}
int main()
{
 int n,m,k;
 cin>>n>>m>>k;
 for(int i=1;i<=n;i++)
  cin>>a[i];
 int siz=sqrt(n);
 for(int i=1;i<=m;i++)
 {
  cin>>q[i].l>>q[i].r;
  q[i].bl=(q[i].l-1)/siz+1;
  q[i].br=(q[i].r-1)/siz+1;
  q[i].id=i;
 }
 sort(q+1,q+m+1,cmp);
 int l=1,r=0;
 for(int i=1;i<=m;i++)
 {
  int ql=q[i].l,qr=q[i].r;
  while(l<ql)
  {
   del(l);
   l++;
  }
  while(l>ql)
  {
   l--;
   add(l);
  }
  while(r<qr)
  {
   r++;
   add(r);
  }
  while(r>qr)
  {
   del(r);
   r--;
  }
  ans[q[i].id]=res;
 }
 for(int i=1;i<=m;i++)
  cout<<ans[i]<<endl;
 return 0;
}

Part 2 带修莫队

之前的题目没有修改操作,如果加上了修改操作,又该如何处理呢?

方法还是很暴力:我们给原来的状态加上一维时间戳,将状态改为 \([l,r,t]\) 的形式。排序和转移的时候考虑一下时间就可以了。

(To be continued…)

发表评论

电子邮件地址不会被公开。 必填项已用*标注