带修改莫队

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

特点

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

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

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

即把询问变成 $[l,r,\text{time}]$ 。

那么我们的坐标也可以在时间维上移动，即 $[l,r,\text{time}]$ 多了一维可以移动的方向，可以变成：

$[l-1,r,\text{time}]$
$[l+1,r,\text{time}]$
$[l,r-1,\text{time}]$
$[l,r+1,\text{time}]$
$[l,r,\text{time}-1]$
$[l,r,\text{time}+1]$

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

可以用和普通莫队类似的方法排序转移，做到 $O(n^{5/3})$ 。

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

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

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

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

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

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

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

接下来分析时间复杂度。

设块长为，则有 $\dfrac{n}{s}$ 个块。对于块和块，记有 $q_{i,j}$ 个询问的左端点位于块，右端点位于块。

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

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

表示一下就是：

\begin{aligned} &\sum_{i=1}^{n/s}\sum_{j=i+1}^{n/s}(q_{i,j}\cdot s+t)\\ =&ms+\left(\dfrac{n}{s}\right)^2t\\ =&ms+\dfrac{n^2t}{s^2} \end{aligned}

考虑求导求此式极小值。设 $f(s)=ms+\dfrac{n^2t}{s^2}$ 。那 $f'(s)=m-\dfrac{2n^2t}{s^3}=0$ 。

得 $s=\sqrt[3]{\dfrac{2n^2t}{m}}=\dfrac{2^{1/3}n^{2/3}t^{1/3}}{m^{1/3}}=s_0$ 。

也就是当块长取 $\dfrac{n^{2/3}t^{1/3}}{m^{1/3}}$ 时有最优时间复杂度 $O\left(n^{2/3}m^{2/3}t^{1/3}\right)$ 。

常说的 $O\left(n^{5/3}\right)$ 便是把当做同数量级的时间复杂度。

实际操作中还是推荐设定 $n^{2/3}$ 为块长。

例题

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

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

修改序列上某一位的数字
询问区间中数字的种类数（多个相同的数字只算一个）

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

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

过程

先考虑普通莫队的做法：

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

现在再来考虑修改：

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

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

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

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

实现

参考代码

#include <bits/stdc++.h>
#define SZ (10005)
using namespace std;

template <typename _Tp>
void IN(_Tp& dig) {
  char c;
  dig = 0;
  while (c = getchar(), !isdigit(c))
    ;
  while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
}

int n, m, sqn, c[SZ], ct[SZ], c1, c2, mem[SZ][3], ans, tot[1000005], nal[SZ];

struct query {
  int l, r, i, c;

  bool operator<(const query another) const {
    if (l / sqn == another.l / sqn) {
      if (r / sqn == another.r / sqn) return i < another.i;
      return r < another.r;
    }
    return l < another.l;
  }
} Q[SZ];

void add(int a) {
  if (!tot[a]) ans++;
  tot[a]++;
}

void del(int a) {
  tot[a]--;
  if (!tot[a]) ans--;
}

char opt[10];

int main() {
  IN(n), IN(m), sqn = pow(n, (double)2 / (double)3);
  for (int i = 1; i <= n; i++) IN(c[i]), ct[i] = c[i];
  for (int i = 1, a, b; i <= m; i++)
    if (scanf("%s", opt), IN(a), IN(b), opt[0] == 'Q')
      Q[c1].l = a, Q[c1].r = b, Q[c1].i = c1, Q[c1].c = c2, c1++;
    else
      mem[c2][0] = a, mem[c2][1] = ct[a], mem[c2][2] = ct[a] = b, c2++;
  sort(Q, Q + c1), add(c[1]);
  int l = 1, r = 1, lst = 0;
  for (int i = 0; i < c1; i++) {
    for (; lst < Q[i].c; lst++) {
      if (l <= mem[lst][0] && mem[lst][0] <= r)
        del(mem[lst][1]), add(mem[lst][2]);
      c[mem[lst][0]] = mem[lst][2];
    }
    for (; lst > Q[i].c; lst--) {
      if (l <= mem[lst - 1][0] && mem[lst - 1][0] <= r)
        del(mem[lst - 1][2]), add(mem[lst - 1][1]);
      c[mem[lst - 1][0]] = mem[lst - 1][1];
    }
    for (++r; r <= Q[i].r; r++) add(c[r]);
    for (--r; r > Q[i].r; r--) del(c[r]);
    for (--l; l >= Q[i].l; l--) add(c[l]);
    for (++l; l < Q[i].l; l++) del(c[l]);
    nal[Q[i].i] = ans;
  }
  for (int i = 0; i < c1; i++) printf("%d\n", nal[i]);
  return 0;
}

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