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}$。这个很重要。。。

代码：

#include <bits/stdc++.h>
#define SZ (10005)
using namespace std;
template<typename _Tp>inline 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;
}

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