基础莫队算法只用于无修改只查询的区间问题，如果是比较简单的单点修改，也能应用莫队算法，时间复杂度是 $O(nm^{\frac{2}{3}})$.

为了能够修改，我们给每个查询 $[l,r]$，增加一个维度时间 $tim$，表示经过的修改次数, 每个查询表示为 $[l,r,tim]$.

那么每个询问 $[l,r,tim]$ 移动方向就可能是:

$[l,r+1,tim],[l-1,r,tim],[l,r-1,tim],[l+1,tim],[l,r,tim-1],[l,r,tim+1]$。

自定义排序

第一关键字为 左端点所在的块，第二关键字为 右端点所在的块，第三关键字为 时间。

时间复杂度

• 先考虑时间维度的修改 从一个询问到另外一个询问，对于任意一个询问 Q ,左侧端点位于第 $i$ 个块，右侧位于第 $j$ 个块内，时间维度上的移动次数就是 $t$ , 两个块 $(i\le j)$ 间移动，移动总次数就是 $\frac{1}{2}(\frac{n}{L})^2 \cdot t$ .

• 再考虑左、右端点移动

  左、右端点都是按所在块排序，块内、块间移动长度 $O(L)$，$m$ 个询问，移动次数是 $mL$ .

$F(L)=\frac{1}{2}\frac{n^2t}{L^2}+mL$

求其导数 $F'(L)=m-n^2tL^{-3}$ ，当 $F'(L)=0$ 时取极值，此时 $L=\sqrt[3]{\frac{n^2t}{m}}$

当 $n,m,t$ 数量级相同时，$L=n^{\frac{2}{3}}$ , 时间复杂度最小，$F(L)=O(n^{\frac{5}{3}})$.

带修莫队的几何解释

第 $i,j$ 块，要满足 $i\le j$ , 实际访问总块数应该是 $\frac{1}{2}\cdot(\frac{n}{L})^2$，几何解释如下：

带修莫队

例1.P1903 【模板】带修莫队 / [国家集训队] 数颜色 / 维护队列

【题意简化】

给你一个序列，$M$ 个操作，有两种操作：

• 修改序列上某一位的数字;
• 询问区间 $[𝑙,𝑟]$ 中数字的种类数（多个相同的数字只算一个）

【分析】

【参考代码】

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=133333+10,M=1e6+10;
int n,m,a[N],tcnt,qcnt,len,cnt[M];
int num,ans[N];
struct node{
    int id,l,r,t;
}Q[N];
struct nodeR{
    int p,c;
}R[N];
bool cmp(node x,node y)
{
    if(x.l/len==y.l/len)
    {
        if(x.r/len==y.r/len)return x.t<y.t;
        return x.r<y.r;
    }
    return x.l<y.l;
}
void add(int x)
{
    cnt[x]++;
    if(cnt[x]==1)num++;  //新增一种颜色
}
void del(int x)
{
    cnt[x]--;
    if(cnt[x]==0)num--;   //减少一种颜色
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=m;i++)
    {
        char op;
        int l,r;
        cin>>op>>l>>r;
        if(op=='Q')
            ++qcnt,Q[qcnt]={qcnt,l,r,tcnt};
        else
            R[++tcnt]={l,r};
    }
    len=pow(n,2.0/3.0);
    sort(Q+1,Q+qcnt+1,cmp);  //离线排序
    int l=1,r=0,now=0;
    for(int i=1;i<=qcnt;i++)
    {
        while(r<Q[i].r)add(a[++r]);
        while(l>Q[i].l)add(a[--l]);
        while(l<Q[i].l)del(a[l++]);
        while(r>Q[i].r)del(a[r--]);

        while(now<Q[i].t)
        {
            now++;
            if(R[now].p>=l && R[now].p<=r)
            {
                del(a[R[now].p]);  //先删除本处的颜色
                add(R[now].c);     //再增加本颜色
            }
            swap(a[R[now].p],R[now].c);//交换是为了往回修改
        }
        while(now>Q[i].t)
        {
            if(R[now].p>=l && R[now].p<=r)
            {
                del(a[R[now].p]); 
                add(R[now].c);    
            }
            swap(a[R[now].p],R[now].c);
            now--;
        }
        ans[Q[i].id]=num;   //保存答案
    }    
    for(int i=1;i<=qcnt;i++)
        cout<<ans[i]<<"\n";
    return 0;
}

例2.CF940F Machine Learning

【题意简化】 给定一个数组 $a$，你需要回答以下两种查询：

1. 给定两个整数 $l$ 和 $r$。令 $c_{i}$ 表示 $a_{l:r}$ 中 $i$ 出现的次数，其中 $a_{l:r}$ 表示从第 $l$ 个元素到第 $r$ 个元素（包含两端）的子数组。请你求出集合 $\{c_{0},c_{1},...,c_{10^{9}}\}$ 的 Mex。
2. 给定两个整数 $p$ 和 $x$。将 $a_{p}$ 改为 $x$。

一个多重集合的 Mex 是指不在该集合中的最小非负整数。

$1 \leq n, q \leq 10^5$

【分析】按照带修莫队，暴力统计 Mex ，时间复杂度为何正确？

$\sum c_i =n$ , 那么集合 ${c_i}$ 次数极限情况就是 ${0,1,2 \cdots x}$ , $0+1+2+...+x=n$ , $x$ 的上限是 $\sqrt{n}$ , 也就是说 $m$ 次询问，每次暴力查找 Mex ，总时间复杂度是 $m\sqrt{n}$ .

【参考代码】点击

学习完毕

{{ select(1) }}

• YES
• NO