Mo's Algorithm

Cửa sổ trượt

Giữ một đoạn hiện tại $[L, R]$ và trạng thái của nó: bảng đếm cnt[x] số lần giá trị $x$ xuất hiện trong đoạn, cộng với đáp án đang có. Dời $R$ sang phải là thêm $a_{R+1}$, dời $L$ sang trái là thêm $a_{L-1}$, dời ngược lại là bỏ. Muốn trả lời câu hỏi $[l, r]$ thì dời hai biên tới đó. Với số giá trị khác nhau: thêm $x$ làm cnt[x] từ 0 lên 1 thì đáp án tăng, bỏ $x$ làm nó về 0 thì đáp án giảm.

Nên mở rộng trước, thu hẹp sau: dời $R$ ra phải và $L$ ra trái trước, rồi mới thu hai biên vào. Làm ngược lại có lúc $L > R + 1$, đoạn “âm” làm cnt âm. Với bảng đếm đơn giản kết quả cuối vẫn đúng, nhưng với trạng thái phức tạp hơn thì sai.

while (R < r) add(++R);
while (L > l) add(--L);
while (R > r) del(R--);
while (L < l) del(L++);

Ví dụGiá Trị Khác Nhau

Đề. Dãy $n \le 3 \cdot 10^4$ số dương tới $10^6$, $q \le 2 \cdot 10^5$ câu hỏi: đếm số giá trị khác nhau trên $[l, r]$.

Lời giải. Thuật toán Mo: giữ một cửa sổ $[L, R]$ cùng bảng đếm cnt theo giá trị và biến cur là số giá trị có cnt > 0. Sắp câu hỏi theo một thứ tự khéo, rồi dời hai biên của cửa sổ từ câu này sang câu kia. Thứ tự câu hỏi giải thích ở mục sau. Giá trị tới $10^6$ nên dùng mảng đếm trực tiếp, không cần nén.

Bước 1: thứ tự câu hỏi. Sắp theo khối của $l$; trong cùng khối thì theo $r$, khối lẻ $r$ giảm, khối chẵn $r$ tăng (mẹo chẵn lẻ ở mục sau). Mỗi câu hỏi giữ id gốc để cuối cùng in đáp án theo thứ tự đầu vào.

bool cmp(query x, query y) {
    if (x.l / B != y.l / B) return x.l < y.l;
    return (x.l / B) & 1 ? x.r > y.r : x.r < y.r;
}

Bước 2: thêm và bỏ một phần tử. Giá trị lần đầu vào cửa sổ thì cur tăng; giá trị rời cửa sổ hẳn thì cur giảm. Cả hai $O(1)$.

void add(ll i) {
    if (cnt[a[i]]++ == 0) cur++;
}

void del(ll i) {
    if (--cnt[a[i]] == 0) cur--;
}

Bước 3: dời cửa sổ. Cửa sổ bắt đầu rỗng với L = 1, R = 0. Mỗi câu hỏi mở rộng hai biên trước rồi mới thu hẹp, để không lúc nào cửa sổ “âm” làm cnt bị trừ quá.

while (R < r) add(++R);
while (L > l) add(--L);
while (R > r) del(R--);
while (L < l) del(L++);
ans[qs[i].id] = cur;

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

const ll N = 3e4 + 5, Q = 2e5 + 5, V = 1e6 + 5;
ll n, q, B, cur, a[N], cnt[V], ans[Q];

struct query {
    ll l, r, id;
} qs[Q];

bool cmp(query x, query y) {
    if (x.l / B != y.l / B) return x.l < y.l;
    return (x.l / B) & 1 ? x.r > y.r : x.r < y.r;
}

void add(ll i) {
    if (cnt[a[i]]++ == 0) cur++;
}

void del(ll i) {
    if (--cnt[a[i]] == 0) cur--;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (ll i = 1; i <= n; i++) cin >> a[i];
    cin >> q;
    for (ll i = 1; i <= q; i++) {
        cin >> qs[i].l >> qs[i].r;
        qs[i].id = i;
    }
    B = max(1LL, (ll)sqrt(n));
    sort(qs + 1, qs + q + 1, cmp);
    ll L = 1, R = 0;
    for (ll i = 1; i <= q; i++) {
        ll l = qs[i].l, r = qs[i].r;
        while (R < r) add(++R);
        while (L > l) add(--L);
        while (R > r) del(R--);
        while (L < l) del(L++);
        ans[qs[i].id] = cur;
    }
    for (ll i = 1; i <= q; i++) cout << ans[i] << '\n';
}

ChạyInput7
4 4 1 2 1 4 3
4
1 7
2 5
3 3
4 7

Output4
3
1
4

Với khối $\sqrt n$, tổng số bước dời là $O((n + q)\sqrt n)$, cộng $O(q \log q)$ để sắp.

Sắp theo khối

Trả lời theo thứ tự đầu vào có thể bắt cửa sổ chạy qua lại cả dãy mỗi câu, $O(nq)$. Mo chia các vị trí thành khối dài $B$, sắp câu hỏi theo khối của $l$, trong cùng khối thì theo $r$ tăng dần. Đếm số bước dời:

• Biên phải. Trong một khối của $l$, $r$ chỉ tăng nên $R$ đi tổng cộng $O(n)$; có $n / B$ khối, tổng $O(n^2 / B)$.
• Biên trái. Hai câu hỏi liên tiếp cùng khối có $l$ lệch nhau dưới $B$; sang khối mới lệch không quá $2B$. Tổng $O(qB)$.

Tổng $O(n^2 / B + qB)$, nhỏ nhất khi $B = n / \sqrt q$, cho $O(n \sqrt q)$. Lấy $B = \sqrt n$ cho $O((n + q)\sqrt n)$, đủ tốt khi $n$ và $q$ cùng cỡ.

Mẹo chẵn lẻ: khối lẻ sắp $r$ giảm dần, khối chẵn sắp $r$ tăng dần, để $R$ không phải chạy từ cuối dãy về đầu mỗi khi đổi khối. Mẹo này chỉ bớt được chừng một phần mười thời gian, còn việc sắp theo khối thì quyết định tất cả:

Sắp kiểu Mo nhanh gấp khoảng 19 lần so với trả lời theo thứ tự đề.

Mỗi bước dời gọi một lần add hoặc del, nên hai hàm này phải $O(1)$, hoặc nhỏ như $O(\log n)$ nếu chấp nhận thêm một thừa số. Bảng đếm theo giá trị là trạng thái điển hình; giá trị lớn thì nén trước.

Ví dụXác Suất Cùng Màu

Đề. Dãy $n \le 5 \cdot 10^4$ màu, $q \le 5 \cdot 10^4$ câu hỏi. Chọn ngẫu nhiên đều hai vị trí khác nhau trong $[l, r]$; in xác suất chúng cùng màu dưới dạng phân số tối giản, không có cặp cùng màu thì 0/1.

Lời giải. Số cặp cùng màu là $\sum_x \binom{c_x}{2}$, tổng số cặp là $\binom{r - l + 1}{2}$. Mo giữ tổng thứ nhất trong cur, cuối cùng chia cả tử và mẫu cho GCD. Với $[1, 6]$, ba màu 1 cho 3 cặp, hai màu 2 cho 1 cặp, trên 15 cặp.

Bước 1: thêm và bỏ. Phần tử màu $x$ mới vào tạo thêm cnt[x] cặp cùng màu với các bản đã có, rồi mới tăng cnt. Bỏ thì giảm trước rồi trừ, đúng là số cặp mất đi.

void add(ll i) {
    cur += cnt[a[i]]++;
}

void del(ll i) {
    cur -= --cnt[a[i]];
}

Bước 2: dời cửa sổ. Thứ tự câu hỏi và bốn vòng dời biên giống hệt ví dụ trước.

Bước 3: rút gọn phân số. tot là số cặp vị trí trong đoạn. Đoạn dài 1 có tot = 0 và cur = 0, rơi vào nhánh 0/1, nên không bao giờ chia cho 0.

ll len = r - l + 1, tot = len * (len - 1) / 2;
if (cur == 0) P[id] = 0, D[id] = 1;
else {
    ll g = __gcd(cur, tot);
    P[id] = cur / g, D[id] = tot / g;
}

Tử và mẫu tới $\binom{5 \cdot 10^4}{2} \approx 1{,}25 \cdot 10^9$, dùng long long.

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

const ll N = 5e4 + 5;
ll n, q, B, cur, a[N], cnt[N], P[N], D[N];

struct query {
    ll l, r, id;
} qs[N];

bool cmp(query x, query y) {
    if (x.l / B != y.l / B) return x.l < y.l;
    return (x.l / B) & 1 ? x.r > y.r : x.r < y.r;
}

void add(ll i) {
    cur += cnt[a[i]]++;
}

void del(ll i) {
    cur -= --cnt[a[i]];
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> q;
    for (ll i = 1; i <= n; i++) cin >> a[i];
    for (ll i = 1; i <= q; i++) {
        cin >> qs[i].l >> qs[i].r;
        qs[i].id = i;
    }
    B = max(1LL, (ll)sqrt(n));
    sort(qs + 1, qs + q + 1, cmp);
    ll L = 1, R = 0;
    for (ll i = 1; i <= q; i++) {
        ll l = qs[i].l, r = qs[i].r, id = qs[i].id;
        while (R < r) add(++R);
        while (L > l) add(--L);
        while (R > r) del(R--);
        while (L < l) del(L++);
        ll len = r - l + 1, tot = len * (len - 1) / 2;
        if (cur == 0) P[id] = 0, D[id] = 1;
        else {
            ll g = __gcd(cur, tot);
            P[id] = cur / g, D[id] = tot / g;
        }
    }
    for (ll i = 1; i <= q; i++) cout << P[i] << '/' << D[i] << '\n';
}

ChạyInput6 4
1 2 1 1 2 3
1 6
2 5
3 3
4 6

Output4/15
1/3
0/1
0/1

$O((n + q)\sqrt n)$ bước dời cửa sổ.

Cặp tiền tố

Câu hỏi đếm các đoạn con của $[l, r]$ có một tính chất cộng tính, như tổng hay XOR bằng $K$, trông không giống câu hỏi về các phần tử. Đặt $p_i = a_1 \oplus \dots \oplus a_i$ và $p_0 = 0$: đoạn con $[i, j]$ có XOR là $p_j \oplus p_{i-1}$. Vậy đếm đoạn con của $[l, r]$ có XOR bằng $K$ là đếm cặp chỉ số $x < y$ trong $[l - 1, r]$ với $p_x \oplus p_y = K$, một câu hỏi về cặp phần tử của mảng tiền tố. Mo chạy trên mảng $p$ với đoạn $[l - 1, r]$; thêm chỉ số $y$ làm tăng đáp án đúng cnt[p[y] ^ K].

Ví dụĐoạn Con XOR Bằng K

Đề. Dãy $n \le 10^5$ số nhỏ hơn $2^{20}$, số $K$, $q \le 10^5$ câu hỏi: đếm số cặp $l \le i \le j \le r$ mà XOR của $a_i, \dots, a_j$ bằng $K$.

Lời giải. Với XOR tiền tố $p_0 = 0$, $p_i = a_1 \oplus \dots \oplus a_i$, XOR của $a_i..a_j$ bằng $p_j \oplus p_{i-1}$. Cặp $(i, j)$ trong $[l, r]$ ứng với cặp chỉ số $u < v$ trong $[l - 1, r]$ có $p_u \oplus p_v = K$. Vậy chạy Mo trên mảng $p$ với đoạn $[l - 1, r]$, đếm số cặp chỉ số trong cửa sổ có XOR bằng $K$.

Bước 1: tiền tố và đổi đoạn. p[i] tính tại chỗ khi đọc. Câu hỏi $[l, r]$ thành $[l - 1, r]$, nên cửa sổ rỗng ban đầu là L = 0, R = -1.

for (ll i = 1; i <= n; i++) {
    cin >> p[i];
    p[i] ^= p[i - 1];
}

Bước 2: thêm và bỏ. Chỉ số mới ghép được với mọi chỉ số cũ có $p$ bằng p[i] ^ k: cộng trước rồi mới tăng cnt[p[i]]. Bỏ thì làm ngược lại theo thứ tự ngược, giảm trước rồi trừ. Khi $K = 0$, p[i] ^ k là chính p[i], và thứ tự này bảo đảm một chỉ số không tự ghép với chính nó.

void add(ll i) {
    cur += cnt[p[i] ^ k];
    cnt[p[i]]++;
}

void del(ll i) {
    cnt[p[i]]--;
    cur -= cnt[p[i] ^ k];
}

Bảng cnt có $2^{20}$ ô vì mọi XOR tiền tố đều dưới $2^{20}$. Thứ tự câu hỏi và vòng dời biên như ví dụ đầu.

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

const ll N = 1e5 + 5, V = 1 << 20;
ll n, q, k, B, cur, p[N], cnt[V], ans[N];

struct query {
    ll l, r, id;
} qs[N];

bool cmp(query x, query y) {
    if (x.l / B != y.l / B) return x.l < y.l;
    return (x.l / B) & 1 ? x.r > y.r : x.r < y.r;
}

void add(ll i) {
    cur += cnt[p[i] ^ k];
    cnt[p[i]]++;
}

void del(ll i) {
    cnt[p[i]]--;
    cur -= cnt[p[i] ^ k];
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> q >> k;
    for (ll i = 1; i <= n; i++) {
        cin >> p[i];
        p[i] ^= p[i - 1];
    }
    for (ll i = 1; i <= q; i++) {
        cin >> qs[i].l >> qs[i].r;
        qs[i].l--;
        qs[i].id = i;
    }
    B = max(1LL, (ll)sqrt(n));
    sort(qs + 1, qs + q + 1, cmp);
    ll L = 0, R = -1;
    for (ll i = 1; i <= q; i++) {
        ll l = qs[i].l, r = qs[i].r;
        while (R < r) add(++R);
        while (L > l) add(--L);
        while (R > r) del(R--);
        while (L < l) del(L++);
        ans[qs[i].id] = cur;
    }
    for (ll i = 1; i <= q; i++) cout << ans[i] << '\n';
}

ChạyInput5 4 3
1 2 3 1 2
1 5
1 3
2 5
4 5

Output4
2
2
1

$O((n + q)\sqrt n)$ bước dời cửa sổ.

Chỉ thêm, không bỏ

Có trạng thái thêm dễ mà bỏ khó: giá trị lớn nhất của một đại lượng chỉ tăng khi thêm, nhưng bỏ đi phần tử đang giữ kỷ lục thì không biết kỷ lục mới là bao nhiêu. Mo chỉ thêm (Mo quay lui, rollback) tránh hẳn thao tác bỏ:

• Xét lần lượt từng khối của $l$. Câu hỏi có $l, r$ cùng một khối thì duyệt thẳng, $O(B)$.
• Các câu hỏi còn lại của khối, sắp theo $r$ tăng dần. Đặt $b$ là cuối khối; phần bên phải $[b + 1, r]$ chỉ lớn dần, nên chỉ thêm.
• Với mỗi câu hỏi, thêm tạm phần trái $[l, b]$ vào trạng thái của phần phải, đọc đáp án, rồi xóa sạch những gì phần trái vừa ghi. Phần trái dài dưới $B$.

Tổng chi phí vẫn $O(n^2 / B + qB)$. Cái giá là phải hoàn tác được phần trái, thường bằng cách ghi riêng nó vào mảng phụ rồi xóa đúng các ô đã ghi; không được xóa cả mảng bằng memset mỗi lần.

Ví dụKhoảng Cách Lặp Lại Xa Nhất

Đề. Dãy $n \le 2 \cdot 10^5$ số, $q \le 2 \cdot 10^5$ câu hỏi: trên $[l, r]$, tìm $j - i$ lớn nhất với $a_i = a_j$, không có cặp nào thì in 0.

Lời giải. Khoảng cách xa nhất không bỏ được dễ dàng: khi một phần tử rời cửa sổ, ta không biết đáp án lùi về bao nhiêu. Vì vậy dùng Mo chỉ thêm (rollback): với các câu hỏi có $l$ cùng khối, phần phải $[b + 1, R]$ (với $b$ là cuối khối) chỉ được thêm vì $r$ tăng dần, còn phần trái $[l, b]$ ngắn hơn một khối được quét lại từ đầu cho mỗi câu hỏi rồi xóa đi.

Bước 1: nén giá trị và sắp câu hỏi. Giá trị nén về $1..n$ để dùng làm chỉ số mảng. Câu hỏi sắp theo khối của $l$, trong khối theo $r$ tăng; không dùng mẹo chẵn lẻ vì phần phải chỉ được thêm.

sort(v + 1, v + n + 1);
for (ll i = 1; i <= n; i++) a[i] = lower_bound(v + 1, v + n + 1, a[i]) - v;

Bước 2: câu hỏi nằm gọn trong khối. Duyệt thẳng, mx[x] nhớ vị trí đầu tiên của $x$; xong thì xóa đúng các ô mx vừa ghi.

if (r <= b) {
    for (ll t = l; t <= r; t++) {
        if (!mx[a[t]]) mx[a[t]] = t;
        res = max(res, t - mx[a[t]]);
    }
    for (ll t = l; t <= r; t++) mx[a[t]] = 0;
    ans[qs[j].id] = res;
    continue;
}

Bước 3: thêm vào phần phải. fst[x], lst[x] là vị trí đầu, cuối của $x$ trong phần phải, cur là đáp án của riêng phần phải; thêm $R$ chỉ có thể làm cur tăng.

while (R < r) {
    R++;
    if (!fst[a[R]]) fst[a[R]] = R;
    lst[a[R]] = R;
    cur = max(cur, R - fst[a[R]]);
}

Bước 4: quét phần trái. Quét từ $b$ lùi về $l$: mx[x] là vị trí lớn nhất của $x$ trong phần trái, tức lần đầu gặp khi quét lùi. Vị trí $t$ ghép xa nhất với lst[x] nếu $x$ có ở phần phải, ngược lại với mx[x]. Quét xong xóa mx; hết khối thì xóa fst, lst trên đúng các vị trí đã thêm.

res = cur;
for (ll t = b; t >= l; t--) {
    if (!mx[a[t]]) mx[a[t]] = t;
    res = max(res, max(lst[a[t]], mx[a[t]]) - t);
}
for (ll t = b; t >= l; t--) mx[a[t]] = 0;

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

const ll N = 2e5 + 5;
ll n, q, B, a[N], v[N], fst[N], lst[N], mx[N], ans[N];

struct query {
    ll l, r, id;
} qs[N];

bool cmp(query x, query y) {
    if (x.l / B != y.l / B) return x.l < y.l;
    return x.r < y.r;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
        v[i] = a[i];
    }
    sort(v + 1, v + n + 1);
    for (ll i = 1; i <= n; i++) a[i] = lower_bound(v + 1, v + n + 1, a[i]) - v;
    cin >> q;
    for (ll i = 1; i <= q; i++) {
        cin >> qs[i].l >> qs[i].r;
        qs[i].id = i;
    }
    B = max(1LL, (ll)sqrt(n));
    sort(qs + 1, qs + q + 1, cmp);
    for (ll i = 1, j; i <= q; i = j) {
        ll blk = qs[i].l / B, b = min(n, (blk + 1) * B - 1), R = b, cur = 0;
        for (j = i; j <= q && qs[j].l / B == blk; j++) {
            ll l = qs[j].l, r = qs[j].r, res = 0;
            if (r <= b) {
                for (ll t = l; t <= r; t++) {
                    if (!mx[a[t]]) mx[a[t]] = t;
                    res = max(res, t - mx[a[t]]);
                }
                for (ll t = l; t <= r; t++) mx[a[t]] = 0;
                ans[qs[j].id] = res;
                continue;
            }
            while (R < r) {
                R++;
                if (!fst[a[R]]) fst[a[R]] = R;
                lst[a[R]] = R;
                cur = max(cur, R - fst[a[R]]);
            }
            res = cur;
            for (ll t = b; t >= l; t--) {
                if (!mx[a[t]]) mx[a[t]] = t;
                res = max(res, max(lst[a[t]], mx[a[t]]) - t);
            }
            for (ll t = b; t >= l; t--) mx[a[t]] = 0;
            ans[qs[j].id] = res;
        }
        for (ll t = b + 1; t <= R; t++) fst[a[t]] = lst[a[t]] = 0;
    }
    for (ll i = 1; i <= q; i++) cout << ans[i] << '\n';
}

ChạyInput8
5 1 5 2 1 5 2 3
5
1 8
2 5
4 8
6 8
3 6

Output5
3
3
0
3

Mỗi khối, phần phải đi tối đa $n$ bước; mỗi câu hỏi quét phần trái tối đa $\sqrt n$ bước: tổng $O((n + q)\sqrt n)$.

Thêm thời gian

Khi dãy bị sửa xen giữa các câu hỏi, thêm chiều thứ ba là thời gian $t$: số lần sửa đã xảy ra trước câu hỏi. Trạng thái giờ là $(L, R, T)$; ngoài bốn vòng dời biên còn vòng dời $T$, mỗi bước áp dụng hoặc hoàn tác một lần sửa. Một lần sửa ở vị trí $p$ nằm trong cửa sổ thì bỏ giá trị cũ và thêm giá trị mới; mẹo gọn là đổi chỗ giá trị trong dãy với giá trị lưu trong lần sửa, nên áp dụng và hoàn tác là cùng một hàm.

Sắp câu hỏi theo khối của $l$, rồi khối của $r$, rồi $t$, với khối dài $B = n^{2/3}$, tức căn bậc ba của $n^2$ (với $n = 10^5$ là khoảng 2150). Biên trái và phải mỗi câu dời $O(B)$, còn $T$ chạy hết $O(q)$ cho mỗi cặp khối, có $(n / B)^2$ cặp. Tổng $O(qB + q n^2 / B^2)$, ở $B = n^{2/3}$ là $O(n^{5/3})$ khi $n$ và $q$ cùng cỡ; với $n = 10^5$ khoảng $2 \cdot 10^8$ bước đơn giản.

Ví dụMàu Sắc Theo Thời Gian

Đề. Dãy $n \le 1{,}33 \cdot 10^5$ màu tới $10^6$, $m$ thao tác cùng cỡ: Q l r đếm số màu khác nhau trên đoạn, R p c đổi màu ô $p$ thành $c$.

Lời giải. Mo có thời gian: thêm chiều thứ ba $t$ là số lần sửa đã áp. Mỗi câu hỏi là bộ ba $(l, r, t)$; cửa sổ dời được theo cả ba chiều. cnt và cur như bài đếm giá trị khác nhau.

Bước 1: tách câu hỏi và lần sửa. Mỗi câu hỏi nhớ t, số lần sửa đứng trước nó; mỗi lần sửa lưu vị trí cp và màu cc.

if (op == 'Q') {
    nq++;
    qs[nq] = {x, y, nc, nq};
} else {
    nc++;
    cp[nc] = x, cc[nc] = y;
}

Bước 2: thứ tự ba khóa. Khối của $l$, rồi khối của $r$, rồi $t$, mỗi khóa sau có mẹo chẵn lẻ. Khối dài $B = n^{2/3}$, tính bằng cbrt(n * n).

bool cmp(query x, query y) {
    if (x.l / B != y.l / B) return x.l < y.l;
    if (x.r / B != y.r / B) return (x.l / B) & 1 ? x.r > y.r : x.r < y.r;
    return (x.r / B) & 1 ? x.t > y.t : x.t < y.t;
}

Bước 3: áp hoặc hoàn tác một lần sửa. Nếu vị trí sửa nằm trong cửa sổ thì bỏ màu cũ, thêm màu mới. Rồi swap màu trong dãy với màu lưu trong lần sửa: gọi lần nữa thì đổi chỗ lại, tức hoàn tác, nên cùng một hàm dùng cho cả hai chiều.

void apply(ll t, ll l, ll r) {
    ll p = cp[t];
    if (l <= p && p <= r) {
        del(a[p]);
        add(cc[t]);
    }
    swap(a[p], cc[t]);
}

Bước 4: dời theo ba chiều. Dời $L$, $R$ trước rồi mới dời $T$, để apply kiểm vị trí sửa với đúng cửa sổ của câu hỏi.

while (R < r) add(a[++R]);
while (L > l) add(a[--L]);
while (R > r) del(a[R--]);
while (L < l) del(a[L++]);
while (T < t) apply(++T, L, R);
while (T > t) apply(T--, L, R);

cnt dùng int cho $10^6$ màu để tiết kiệm bộ nhớ.

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

const ll N = 1.4e5, V = 1e6 + 5;
ll n, m, B, cur, nq, nc, a[N], cp[N], cc[N], ans[N];
int cnt[V];

struct query {
    ll l, r, t, id;
} qs[N];

bool cmp(query x, query y) {
    if (x.l / B != y.l / B) return x.l < y.l;
    if (x.r / B != y.r / B) return (x.l / B) & 1 ? x.r > y.r : x.r < y.r;
    return (x.r / B) & 1 ? x.t > y.t : x.t < y.t;
}

void add(ll x) {
    if (cnt[x]++ == 0) cur++;
}

void del(ll x) {
    if (--cnt[x] == 0) cur--;
}

void apply(ll t, ll l, ll r) {
    ll p = cp[t];
    if (l <= p && p <= r) {
        del(a[p]);
        add(cc[t]);
    }
    swap(a[p], cc[t]);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (ll i = 1; i <= n; i++) cin >> a[i];
    for (ll i = 1; i <= m; i++) {
        char op;
        ll x, y;
        cin >> op >> x >> y;
        if (op == 'Q') {
            nq++;
            qs[nq] = {x, y, nc, nq};
        } else {
            nc++;
            cp[nc] = x, cc[nc] = y;
        }
    }
    B = max(1LL, (ll)cbrt((double)n * n));
    sort(qs + 1, qs + nq + 1, cmp);
    ll L = 1, R = 0, T = 0;
    for (ll i = 1; i <= nq; i++) {
        ll l = qs[i].l, r = qs[i].r, t = qs[i].t;
        while (R < r) add(a[++R]);
        while (L > l) add(a[--L]);
        while (R > r) del(a[R--]);
        while (L < l) del(a[L++]);
        while (T < t) apply(++T, L, R);
        while (T > t) apply(T--, L, R);
        ans[qs[i].id] = cur;
    }
    for (ll i = 1; i <= nq; i++) cout << ans[i] << '\n';
}

ChạyInput5 7
1 2 1 3 2
Q 1 5
R 3 2
Q 1 3
R 4 1
Q 2 5
R 1 2
Q 1 4

Output3
2
2
2

Với $B = n^{2/3}$, tổng số bước dời là $O(n^{5/3})$.