「Luogu P1903」「国家集训队」数颜色/维护队列

Description

给定 $n$ 个数，$m$ 次操作，操作分两种：

Q L R：询问区间 $[L,R]$ 中有多少个不同的数；

R P Col：把第 $P$ 个数替换为 $Col$ 。

$(1 \leq n,m \leq 5 \times 10^4$，数的大小均大于等于 $1$ 且不超过 $10^6)$

Source

[Luogu]P1903

Solution

看到这道题的询问，就很容易想到 莫队 。可是还有修改操作，普通的莫队不支持，怎么办呢？带修莫队 应运而生。

带修莫队，字面意思即是带修改的莫队。它与普通莫队不同的是，多了一个 时间戳，用来记录到当前这个询问时已经进行了多少次修改操作。

我们把询问和修改分别存下来。对于每一个询问，我们不仅要做到左右端点与当前询问一致，还要使修改次数与当前询问相同。如果我们修改得过多，那么应该删去多余的修改，修改过少则反之。

普通莫队写法：

for (; l > ql; add(col[--l]));
for (; r < qr; add(col[++r]));
for (; l < ql; del(col[l++]));
for (; r > qr; del(col[r--]));

带修莫队新增的两句话：

for (; t < qt; upd(++t, i));
for (; t > qt; upd(t--, i));

其中 $qt$ 表示这个询问已修改的次数，$t$ 表示当前已修改的次数，$i$ 表示排序后是第 $i$ 个询问。

upd 操作：

inline void upd(int x, int i) {//在第 i 个询问进行第 x 次修改
    if (u[x].pos >= q[i].l && u[x].pos <= q[i].r) {//修改的位置在询问区间内才会产生影响 
        del(col[u[x].pos]);//删掉第 pos 位上的数 
        add(u[x].k);//增加修改完的数 
    }
    swap(col[u[x].pos], u[x].k);
    //如果我们这一次修改把 x 变成了 y，下次如果要改回来就不是把 x 变成 y 了，
    //而是应当把 y 变成 x，所以我们修改完后我们要把 x 和 y 交换
}

至于排序，和普通莫队大致相同。

普通排序：

if (x.l / blockSize != y.l / blockSize) return x.l < y.l;
else if (x.r / blockSize != y.r / blockSize) return x.r < y.r;
return x.t < y.t;

若左端点不在同一块，则按左端点排序；若左端点在同一块，右端点不在同一块，则按右端点排序；若都在同一块，则按修改次数排序。

奇偶性排序：

if (x.l / blockSize != y.l / blockSize) return x.l < y.l;
else if (x.r / blockSize != y.r / blockSize)
    return ((x.l / blockSize) & 1) ? x.r < y.r : x.r > y.r;
return x.t < y.t;

若左端点在同一块，右端点不在同一块，则根据左端点所在块编号的奇偶性对右端点排序。其它与普通排序相同。

在带修莫队中，块的大小（$blockSize$）设 $n^{\frac{2}{3}}$ 比较快。此时的时间复杂度约为 $O(n^{\frac{5}{3}})$，证明有些麻烦，这里暂不给出。

Code

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

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

inline void readChar(char &c) {
    for (c = getchar(); c != 'Q' && c != 'R'; c = getchar());
}

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
    int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

const int MAXN = 5e4, MAXM = 1e6;
int n, m, cntQ, cntR, res, blockSize, ans[MAXN + 5], col[MAXN + 5], cnt[MAXM + 5];
struct Query {
    int l, r, t, id;
    //l = 左端点，r = 右端点，t = 已修改次数（时间戳），id = 询问编号
    inline friend bool operator<(Query x, Query y) {
        if (x.l / blockSize != y.l / blockSize) return x.l < y.l;
        else if (x.r / blockSize != y.r / blockSize)
            return ((x.l / blockSize) & 1) ? x.r < y.r : x.r > y.r;
        return x.t < y.t;
    }
} q[MAXN + 5];
struct Update {
    int pos, k;//把第 pos 个数变为 k 
} u[MAXN + 5];

inline void add(int x) {
    res += !cnt[x];
    ++cnt[x];
}

inline void del(int x) {
    --cnt[x];
    res -= !cnt[x];
}

inline void upd(int x, int i) {//在第 i 个询问进行第 x 次修改
    if (u[x].pos >= q[i].l && u[x].pos <= q[i].r) {//修改的位置在询问区间内才会产生影响 
        del(col[u[x].pos]);//删掉第 pos 位上的数 
        add(u[x].k);//增加修改完的数 
    }
    swap(col[u[x].pos], u[x].k);
    //如果我们这一次修改把 x 变成了 y，下次如果要改回来就不是把 x 变成 y 了，
    //而是应当把 y 变成 x，所以我们修改完后我们要把 x 和 y 交换
}

inline void mo() {
    sort(q + 1, q + cntQ + 1);
    int l = 1, r = 0, t = 0;//初始左端点为 1，右端点为 0，进行了 0 次修改 
    for (int i = 1; i <= cntQ; ++i) {
        int ql = q[i].l, qr = q[i].r, qt = q[i].t;
        for (; l > ql; add(col[--l]));
        for (; r < qr; add(col[++r]));
        for (; l < ql; del(col[l++]));
        for (; r > qr; del(col[r--]));
        for (; t < qt; upd(++t, i));
        for (; t > qt; upd(t--, i));
        ans[q[i].id] = res;
    }
}

int main() {
    read(n), read(m);
    blockSize = pow(n, 2.0 / 3);
    for (int i = 1; i <= n; ++i) read(col[i]);//初始颜色 
    for (int i = 1; i <= m; ++i) {
        char opt;
        readChar(opt);
        if (opt == 'Q') {//记录共 cntQ 个修改 
            read(q[++cntQ].l), read(q[cntQ].r);
            q[cntQ].t = cntR, q[cntQ].id = cntQ;
        } else read(u[++cntR].pos), read(u[cntR].k);//记录共 cntR 个修改 
    }
    mo();
    for (int i = 1; i <= cntQ; ++i) {
        write(ans[i]);
        putchar('\n');
    }
    return 0;
}