带修改莫队

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

普通莫队算法。

特点

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

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

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

即把询问 变成 。

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

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

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

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

例题

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

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

过程

先考虑普通莫队的做法：

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

现在再来考虑修改：

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

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

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

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

实现