跳转至

# 带修改莫队

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

## 特点

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

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

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

即把询问 [𝑙,𝑟][l,r] 变成 [𝑙,𝑟,t i m e][l,r,time]．

那么我们的坐标也可以在时间维上移动，即 [𝑙,𝑟,t i m e][l,r,time] 多了一维可以移动的方向，可以变成：

- [𝑙 −1,𝑟,t i m e][l−1,r,time]
- [𝑙 +1,𝑟,t i m e][l+1,r,time]
- [𝑙,𝑟 −1,t i m e][l,r−1,time]
- [𝑙,𝑟 +1,t i m e][l,r+1,time]
- [𝑙,𝑟,t i m e −1][l,r,time−1]
- [𝑙,𝑟,t i m e +1][l,r,time+1]

这样的转移也是 𝑂(1)O(1) 的，但是我们排序又多了一个关键字，再搞搞就行了．

可以用和普通莫队类似的方法排序转移，做到 𝑂(𝑛 5/3)O(n 5/3)．

这一次我们排序的方式是以 𝑛 2/3 n 2/3 为一块，分成了 𝑛 1/3 n 1/3 块，第一关键字是左端点所在块，第二关键字是右端点所在块，第三关键字是时间．

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

我们设序列长为 𝑛 n，𝑚 m 个询问，𝑡 t 个修改．

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

想一想，如果不把右端点分块：

- 乱序的右端点对于每个询问会移动 𝑛 n 次．
- 有序的右端点会带来乱序的时间，每次询问会移动 𝑡 t 次．

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

接下来分析时间复杂度．

设块长为 𝑠 s，则有 𝑛 𝑠 n s 个块．对于块 𝑖 i 和块 𝑗 j，记有 𝑞 𝑖,𝑗 q i,j 个询问的左端点位于块 𝑖 i，右端点位于块 𝑗 j．

每「组」左右端点不换块的询问 (𝑖,𝑗)(i,j)，端点每次移动 𝑂(𝑠)O(s) 次，时间单调递增，𝑂(𝑡)O(t)．

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

表示一下就是：

𝑛/𝑠∑𝑖=1 𝑛/𝑠∑𝑗=𝑖+1(𝑞 𝑖,𝑗⋅𝑠+𝑡)=𝑚 𝑠+(𝑛 𝑠)2 𝑡=𝑚 𝑠+𝑛 2 𝑡 𝑠 2∑i=1 n/s∑j=i+1 n/s(q i,j⋅s+t)=m s+(n s)2 t=m s+n 2 t s 2

考虑求导求此式极小值．设 𝑓(𝑠) =𝑚 𝑠 +𝑛 2 𝑡 𝑠 2 f(s)=m s+n 2 t s 2．那 𝑓′(𝑠) =𝑚 −2 𝑛 2 𝑡 𝑠 3 =0 f′(s)=m−2 n 2 t s 3=0．

得 𝑠 =3√2 𝑛 2 𝑡 𝑚 =2 1/3 𝑛 2/3 𝑡 1/3 𝑚 1/3 =𝑠 0 s=2 n 2 t m 3=2 1/3 n 2/3 t 1/3 m 1/3=s 0．

也就是当块长取 𝑛 2/3 𝑡 1/3 𝑚 1/3 n 2/3 t 1/3 m 1/3 时有最优时间复杂度 𝑂(𝑛 2/3 𝑚 2/3 𝑡 1/3)O(n 2/3 m 2/3 t 1/3)．

常说的 𝑂(𝑛 5/3)O(n 5/3) 便是把 𝑛,𝑚,𝑡 n,m,t 当做同数量级的时间复杂度．

实际操作中还是推荐设定 𝑛 2/3 n 2/3 为块长．

## 例题

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

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

1. 修改序列上某一位的数字
2. 询问区间 [𝑙,𝑟][l,r] 中数字的种类数（多个相同的数字只算一个）

我们不难发现，如果不带操作 1（修改）的话，我们就能轻松用普通莫队解决．

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

### 过程

先考虑普通莫队的做法：

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

现在再来考虑修改：

- 单点修改，把某一位的数字修改掉．假如我们是从一个经历修改次数为 𝑖 i 的询问转移到一个经历修改次数为 𝑗 j 的询问上，且 𝑖 <𝑗 i<j 的话，我们就需要把第 𝑖 +1 i+1 个到第 𝑗 j 个修改强行加上．
- 假如 𝑗 <𝑖 j<i 的话，则需要把第 𝑖 i 个到第 𝑗 +1 j+1 个修改强行还原．

怎么强行加上一个修改呢？假设一个修改是修改第 𝑝 𝑜 𝑠 p o s 个位置上的颜色，原本 𝑝 𝑜 𝑠 p o s 上的颜色为 𝑎 a，修改后颜色为 𝑏 b，还假设当前莫队的区间扩展到了 [𝑙,𝑟][l,r]．

- 加上这个修改：我们首先判断 𝑝 𝑜 𝑠 p o s 是否在区间 [𝑙,𝑟][l,r] 内．如果是的话，我们等于是从区间中删掉颜色 𝑎 a，加上颜色 𝑏 b，并且当前颜色序列的第 𝑝 𝑜 𝑠 p o s 项的颜色改成 𝑏 b．如果不在区间 [𝑙,𝑟][l,r] 内的话，我们就直接修改当前颜色序列的第 𝑝 𝑜 𝑠 p o s 项为 𝑏 b．
- 还原这个修改：等于加上一个修改第 𝑝 𝑜 𝑠 p o s 项、把颜色 𝑏 b 改成颜色 𝑎 a 的修改．

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

### 实现

参考代码

     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
    #include <algorithm>
    #include <cmath>
    #include <iostream>
    using namespace std;

    long long qsize;

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

      bool operator<(query b) const {
        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 {
      long long p, x;
    } r[150009];

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

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

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

    void process() {
      sort(q + 1, q + qcnt + 1);
      long long L = 1, R = 0, last = 0;
      for (long long 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(nullptr);
      ios::sync_with_stdio(false);
      cin >> n >> m;
      qsize = pow(n, 2.0 / 3.0);
      for (long long i = 1; i <= n; i++) {
        cin >> a[i];
      }
      for (long long i = 1; i <= m; i++) {
        cin >> op >> x >> y;
        if (op == 'Q') {
          ++qcnt, q[qcnt] = {qcnt, rcnt, x, y};
        } else if (op == 'R') {
          r[++rcnt] = {x, y};
        }
      }
      process();
      for (long long i = 1; i <= qcnt; i++) {
        cout << ans[i] << '\n';
      }
    }

> 本页面最近更新：2026/1/7 08:56:54，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：Backl1ght, countercurrent-time, Ir1d, Lixuannan, renbaoshuo, Tiphereth-A, 2008verser, 383494, c-forrest, CCXXXI, Chrogeek, Enter-tainer, greyqz, Henry-ZHR, iamtwz, kenlig, MicDZ, O-Omega, ouuan, StudyingFather, yzxoi
> 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用