Pre

请确保您已经会普通莫队算法了。
如果您还不会,请食用这篇博客:【算法】 普通莫队算法

特点

  • 用于离线处理区间问题
  • 仅含单点修改
  • 能$O(1)$转移区间(和普通莫队一样)
  • 分块的每一块的大小是$n^\frac{2}{3}$
  • 复杂度$O(n^\frac{5}{3})$

带修改的莫队的询问排序方法为:

  • 第一关键字:左端点所在块编号,从小到大排序。
  • 第二关键字:右端点所在块编号,从小到大排序。
  • 第三关键字:经历的修改次数。也可以说是询问的先后,先询问的排前面。

对于前后两个区间的转移:

设当前询问为$a$,下一个询问为$b$,我们已知$a$,要求$b$。

首先我们像普通莫队一样转移左右端点。

这时候我们可能会发现$a$和$b$的经历的修改次数不同

怎么办呢?

然而,莫队就是个优雅的暴力。

假如$a$较$b$少修改了$p$次,那我们就把这$p$次修改一个一个从前往后暴力地加上去。假如$a$较$b$多修改了$q$次,那我们就把这$q$次修改从后往前还原掉。

具体怎么做呢?我们来看一道例题。

例题

数颜色 BZOJ - 2120

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

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

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

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

先考虑普通莫队的做法:

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

现在再来考虑修改:

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

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

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

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

记得前面说的一些普通莫队与带修改莫队不同的地方就行了,比如分块的每一块的大小是$n^\frac{2}{3}$。这个很重要。。。

代码:

//因为本人太弱,所以可能讲得有点不到位,还请多多包涵。。。= ̄ω ̄=