前置知识:分块, 基础莫队

$$带修莫队$$

$简介$

在普通莫队基础上,增加了修改操作

$基本操作$

给定长度为$n$的序列

可支持以下$2$种操作：
1. p c将序列中第$p$个位置上的数改为$c$
2. l r询问$[l,r]$中的某种可加减性属性

$思想$

由于增加修改操作,考虑给每一个修改操作按先后顺序编号

将一维改为二维,纵坐标为时间 $time$ ,横坐标为位置 $l,r$

当时间为 $k$ 时,表示已经经过了前 $k$ 个修改操作

若序列长度为 $n$ ,分块后每段长度为 $a$ ,共有 $\frac{n}{a}$ 块, $m$ 次询问, $t$ 次修改(根据数据范围,取合适的 $len$ )

$i$ 表示左指针, $j$ 表示右指针, $time$ 表示时间戳

排序标准为：
1. 比较左端点所在的块,从左到右排序
2. 若左端点所在块相同,则比较右端点所在块,从从左到右排序
3. 若右端点所在块也相同,则比较时间 $times$ ,从左到右排序

指针 $time$ 移动次数: $\frac{n^2t}{a^2}$
指针 $i$ 移动次数: $am+n$
指针 $j$ 移动次数: $am+\frac{n^2}{a}$

实现

#include <bits/stdc++.h>
using namespace std;

const int N = 134514, S = 1000010;
int n, m, times, mq, len;
int a[N], ans[N], cnt[S];
struct Query{
    int l, r, t, id;
}Q[N];
struct Modify{
    int p, c;
}M[N];

int get(int i)
{
    return i / len;
}

bool cmp(Query a, Query b)
{
    int al = get(a.l), bl = get(b.l);
    int ar = get(a.r), br = get(b.r);
    if (al != bl)return al < bl;
    if (ar != br)return ar < br;
    return a.t < b.t;
}

void add(int x, int& res)
{
    if (!cnt[x])res ++ ;
    cnt[x] ++ ;
}

void del(int x, int& res)
{
    cnt[x] -- ;
    if (!cnt[x])res -- ;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ )scanf("%d", &a[i]);
    for (int i = 1; i <= m; i ++ )
    {
        char op[2];
        int a, b;
        scanf("%s%d%d", op, &a, &b);
        if (*op == 'Q')mq ++ , Q[mq] = {a, b, times, mq};
        else M[++ times] = {a, b};
    }
    len = cbrt((double)n * max(times, 1)) + 1;
    sort(Q + 1, Q + mq + 1, cmp);
    for (int k = 1, i = 1, j = 0, t = 0, res = 0; k <= mq; k ++ )
    {
        int l = Q[k].l, r = Q[k].r, tm = Q[k].t, id = Q[k].id;
        while (t < tm)
        {
            t ++ ;
            if (M[t].p >= i && M[t].p <= j)
            {
                add(M[t].c, res);
                del(a[M[t].p], res);
            }
            swap(a[M[t].p], M[t].c);
        }
        while (t > tm)
        {
            if (M[t].p >= i && M[t].p <= j)
            {
                add(M[t].c, res);
                del(a[M[t].p], res);
            }
            swap(a[M[t].p], M[t].c);
            t -- ;
        }
        while (i < l)del(a[i ++ ], res);
        while (i > l)add(a[ -- i], res);
        while (j < r)add(a[ ++ j], res);
        while (j > r)del(a[j -- ], res);
        ans[id] = res;
    }
    for (int i = 1; i <= mq; i ++ )printf("%d\n", ans[i]);
    return 0;
}