『学习笔记』莫队

cyf1208 / 2024-02-18 / 原文

Part 0. 目录

概念
普通莫队
树上莫队
带修莫队

Part 1. 概念

莫队是由莫涛提出的算法。莫队算法可以解决一类离线区间询问问题，适用性极为广泛。

Part 2. 普通莫队

普通莫队主要针对于多次区间询问的问题，基于分块的思想。

过程如下：

先将当前区间 $[l,r]$ 设为 $[1,0]$，再每次移动一个端点，即变为 $[l-1,r],[l,r+1],[l+1,r],[l,r-1]$。也就是说每次移动长度会加 $1$ 或减 $1$，从而会多一个元素或减一个元素，进而我们就产生了两个用于在移动时记录答案的函数 $\operatorname{add}$ 和 $\operatorname{del}$。

调用的代码如下：

inline void add(int x) {
  //...
}
inline void del(int x) {
  //...
}
sort(q + 1, q + m + 1);
int l = 1, r = 0;
for(int i = 1; i <= m; i++) {
  while(l > q[i].l) { add(a[--l]); }
  while(r < q[i].r) { add(a[++r]); }
  while(l < q[i].l) { del(a[l++]); }
  while(r > q[i].r) { del(a[r--]); }
  ans[q[i].id] = sum;
}

而排序怎么排以及块长 $bl$ 取多少就决定了代码的时间复杂度。

一般的排序方式是先按左端点所在块为第一关键字，再按右端点为第二关键字排序，代码如下：

return b[l] != b[x.l] ? l < x.l : r < x.r;

但对于这种：

画框部分就多移动了两遍，于是我们考虑奇偶化排序，也就是若左端点所在块相等，则若为奇数块，则按右端点升序排序；否则按右端点降序排序。

代码如下：

return b[l] != b[x.l] ? l < x.l : (r == x.r ? 0 : (b[l] & 1) ^ (r < x.l));

此时排序情况如下，很明显减少了一倍的移动量。

时间复杂度为 $\mathcal{O}\left(m(\sqrt{n}+\log_2m)\right)$。

接着便是一堆例题。

SP3267 & P1972

题目链接：link1 and link2。

题目大意：每次询问求区间 $[l,r]$ 内的权值种数。

题目的关键在于 $\operatorname{add}$ 和 $\operatorname{del}$ 两个函数。

对于一个数 $a_i$，在它刚进入区间 $[l,r]$ 时，那么 $a_i$ 出现的个数加 $1$，若它之前未出现过，代表种数多 $1$。

同理，在它刚离开区间 $[l,r]$ 时，$a_i$ 出现的个数减 $1$，若现在其个数为 $0$，代表种数少 $1$。

两个函数代码如下：

inline void add(int x) { sum += !cnt[x]++; }
inline void del(int x) { sum -= !--cnt[x]; }

PS：P1972 需要卡常，莫队并非正解，但卡的过去。

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 5;
int n, m, c[N], bl, b[N], sum = 0, cnt[N], ans[N];
struct node {
  int l, r, id;
  bool operator < (const node &x) const {
    if(b[l] != b[x.l]) { return b[l] < b[x.l]; }
    return r < x.r;
  }
} a[N];
inline void add(int x) { sum += !cnt[x]++; }
inline void del(int x) { sum -= !--cnt[x]; }
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n;
  bl = sqrt(n + 1);
  for(int i = 1; i <= n; i++) {
    cin >> c[i];
    b[i] = (i - 1) / bl + 1;
  }
  cin >> m;
  for(int i = 1; i <= m; i++) {
    cin >> a[i].l >> a[i].r;
    a[i].id = i;
  }
  sort(a + 1, a + m + 1);
  int l = 1, r = 0;
  for(int i = 1; i <= m; i++) {
    while(l > a[i].l) { add(c[--l]); }
    while(r < a[i].r) { add(c[++r]); }
    while(l < a[i].l) { del(c[l++]); }
    while(r > a[i].r) { del(c[r--]); }
    ans[a[i].id] = sum;
  }
  for(int i = 1; i <= m; i++) {
    cout << ans[i] << '\n';
  }
  return 0;
}

P1494

题目链接：link。

题目大意：令区间 $[l,r]$ 内 $x$ 出现了 $c_x$ 次，求 $\dfrac{\sum c_x\times(c_x-1)\div2}{(r-l+1)\times(r-l)\div2}$。

同样是两个函数，但很好处理，每次 $sum$ 加或减 $c_x$ 即可。

P2709

题目链接：link。

题目大意：求 $\sum {c_x}^2$。

对于每次移动，$sum$ 加或减 $(c_x+1)^2-{c_x}^2=2c_x+1$。

CF1000F

题目链接：link。

题目大意：求任意一个 $c_x=1$ 的 $x$。

用一个栈来存满足条件的 $x$。

点击查看代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n, m, a[N], bl, sum = 0, cnt[N], ans[N];
int b[N], c[N], tot;
struct node {
  int l, r, b, id;
  bool operator < (const node &x) const {
    if(b != x.b) { return b < x.b; }
    return r == x.r ? 0 : (b & 1) ^ (r < x.r);
  }
} q[N];
inline void add(int x) {
  ++cnt[x];
  if(cnt[x] == 1) {
    ++sum;
    b[++tot] = x;
    c[x] = tot;
  }
  if(cnt[x] == 2) {
    --sum;
    b[c[x]] = b[tot];
    c[b[tot]] = c[x];
    b[tot--] = c[x] = 0;
  }
}
inline void del(int x) {
  --cnt[x];
  if(cnt[x] == 1) {
    ++sum;
    b[++tot] = x;
    c[x] = tot;
  }
  if(cnt[x] == 0) {
    --sum;
    b[c[x]] = b[tot];
    c[b[tot]] = c[x];
    b[tot--] = c[x] = 0;
  }
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n;
  bl = sqrt(n);
  for(int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  cin >> m;
  for(int i = 1; i <= m; i++) {
    cin >> q[i].l >> q[i].r;
    q[i].b = q[i].l / bl, q[i].id = i;
  }
  sort(q + 1, q + m + 1);
  int l = 1, r = 0;
  for(int i = 1; i <= m; i++) {
    while(l > q[i].l) { add(a[--l]); }
    while(r < q[i].r) { add(a[++r]); }
    while(l < q[i].l) { del(a[l++]); }
    while(r > q[i].r) { del(a[r--]); }
    if(sum) {
      ans[q[i].id] = b[tot];
    }
  }
  for(int i = 1; i <= m; i++) {
    cout << ans[i] << '\n';
  }
  return 0;
}

CF220B

题目链接：link。

题目大意：有多少个 $x$ 满足 $c_x=x$。

对于 $\operatorname{add}$ 函数，如果 $c_x\gets c_x+1$ 后 $c_x=x$，满足条件，答案加 $1$；如果 $c_x=x+1$，代表这个 $x$ 本来满足条件，现在不满足了，答案减 $1$。$\operatorname{del}$ 函数同理。

两个函数代码如下：

inline void add(int x) {
  if(x > n) { return ; }
  ++cnt[x];
  if(cnt[x] == x) { ++sum; }
  if(cnt[x] == x + 1) { --sum; }
}
inline void del(int x) {
  if(x > n) { return ; }
  --cnt[x];
  if(cnt[x] == x) { ++sum; }
  if(cnt[x] == x - 1) { --sum; }
}