跳转至

带修改莫队

请确保您已经会普通莫队算法了。如果您还不会,请先阅读前面的 普通莫队算法

特点

普通莫队是不能带修改的。

我们可以强行让它可以修改,就像 DP 一样,可以强行加上一维 时间维, 表示这次操作的时间。

时间维表示经历的修改次数。

即把询问 变成

那么我们的坐标也可以在时间维上移动,即 多了一维可以移动的方向,可以变成:

这样的转移也是 的,但是我们排序又多了一个关键字,再搞搞就行了。

可以用和普通莫队类似的方法排序转移,做到

这一次我们排序的方式是以 为一块,分成了 块,第一关键字是左端点所在块,第二关键字是右端点所在块,第三关键字是时间。

最优块长以及时间复杂度分析

我们设序列长为 个询问, 个修改。

带修莫队排序的第二关键字是右端点所在块编号,不同于普通莫队。

想一想,如果不把右端点分块:

  • 乱序的右端点对于每个询问会移动 次。
  • 有序的右端点会带来乱序的时间,每次询问会移动 次。

无论哪一种情况,带来的时间开销都无法接受。

接下来分析时间复杂度。

设块长为 ,则有 个块。对于块 和块 ,记有 个询问的左端点位于块 ,右端点位于块

每「组」左右端点不换块的询问 ,端点每次移动 次,时间单调递增,

左右端点换块的时间忽略不计。

表示一下就是:

考虑求导求此式极小值。设 。那

也就是当块长取 时有最优时间复杂度

常说的 便是把 当做同数量级的时间复杂度。

实际操作中还是推荐设定 为块长。

例题

例题 「国家集训队」数颜色/维护队列

题目大意:给你一个序列,M 个操作,有两种操作:

  1. 修改序列上某一位的数字
  2. 询问区间 中数字的种类数(多个相同的数字只算一个)

我们不难发现,如果不带操作 1(修改)的话,我们就能轻松用普通莫队解决。

但是题目还带单点修改,所以用 带修改的莫队

过程

先考虑普通莫队的做法:

  • 每次扩大区间时,每加入一个数字,则统计它已经出现的次数,如果加入前这种数字出现次数为 ,则说明这是一种新的数字,答案 。然后这种数字的出现次数
  • 每次减小区间时,每删除一个数字,则统计它删除后的出现次数,如果删除后这种数字出现次数为 ,则说明这种数字已经从当前的区间内删光了,也就是当前区间减少了一种颜色,答案 。然后这种数字的出现次数

现在再来考虑修改:

  • 单点修改,把某一位的数字修改掉。假如我们是从一个经历修改次数为 的询问转移到一个经历修改次数为 的询问上,且 的话,我们就需要把第 个到第 个修改强行加上。
  • 假如 的话,则需要把第 个到第 个修改强行还原。

怎么强行加上一个修改呢?假设一个修改是修改第 个位置上的颜色,原本 上的颜色为 ,修改后颜色为 ,还假设当前莫队的区间扩展到了

  • 加上这个修改:我们首先判断 是否在区间 内。如果是的话,我们等于是从区间中删掉颜色 ,加上颜色 ,并且当前颜色序列的第 项的颜色改成 。如果不在区间 内的话,我们就直接修改当前颜色序列的第 项为
  • 还原这个修改:等于加上一个修改第 项、把颜色 改成颜色 的修改。

因此这道题就这样用带修改莫队轻松解决啦!

实现

参考代码
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
#include <algorithm>
#include <cmath>
#include <iostream>

#define int long long
#define endl '\n'

using namespace std;

int qsize;

struct query {
  int id, t, l, r;

  inline bool operator<(query b) {
    if (l / qsize != b.l / qsize) {
      return l / qsize > b.l / qsize;
    } else if (r / qsize != b.r / qsize) {
      return r / qsize > b.r / qsize;
    } else {
      return t > b.t;
    }
  }
} q[150009];

struct operation {
  int p, x;
} r[150009];

char op;
int n, m, x, y, cur, qcnt, rcnt, mp[1500009], a[150009], ans[150009];

inline void add(int x) {
  if (!mp[x]) {
    cur += 1;
  }
  mp[x] += 1;
}

inline void del(int x) {
  mp[x] -= 1;
  if (!mp[x]) {
    cur -= 1;
  }
}

inline void process() {
  sort(q + 1, q + qcnt + 1);
  int L = 1, R = 0, last = 0;
  for (int i = 1; i <= qcnt; i++) {
    while (R < q[i].r) {
      add(a[++R]);
    }
    while (R > q[i].r) {
      del(a[R--]);
    }
    while (L > q[i].l) {
      add(a[--L]);
    }
    while (L < q[i].l) {
      del(a[L++]);
    }
    while (last < q[i].t) {
      last += 1;
      if (r[last].p >= L && r[last].p <= R) {
        add(r[last].x);
        del(a[r[last].p]);
      }
      swap(a[r[last].p], r[last].x);
    }
    while (last > q[i].t) {
      if (r[last].p >= L && r[last].p <= R) {
        add(r[last].x);
        del(a[r[last].p]);
      }
      swap(a[r[last].p], r[last].x);
      last -= 1;
    }
    ans[q[i].id] = cur;
  }
}

signed main() {
  cin.tie(0);
  cout.tie(0);
  ios::sync_with_stdio(false);
  cin >> n >> m;
  qsize = pow(n, 2.0 / 3.0);
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i <= m; i++) {
    cin >> op >> x >> y;
    if (op == 'Q') {
      q[++qcnt] = {qcnt, rcnt, x, y};
    } else if (op == 'R') {
      r[++rcnt] = {x, y};
    }
  }
  process();
  for (int i = 1; i <= qcnt; i++) {
    cout << ans[i] << endl;
  }
}