8.9K 674 107

Đã đăng vào thg 1 19, 8:00 SA 17 phút đọc

396

Chia căn (phần 2) - Mo's algorithm

Đây là bài viết số $2$ thuộc series Chia căn, thuộc danh sách bài viết về Cấu trúc dữ liệu nâng cao và Các kĩ thuật tối ưu hóa. Trước khi đọc bài viết này, các bạn cần nắm vững cơ bản về kĩ thuật Chia căn. Các bạn có thể xem lại bài viết phần $1$ về Chia căn tại đây.

I. Giới thiệu chung

Ở bài viết phần $1,$ chúng ta đã cùng thảo luận về kĩ thuật Chia căn cơ bản - là kĩ thuật rất hiệu quả để giải quyết các bài toán truy vấn và cập nhật đoạn với input không quá lớn (khoảng $n \le 10^5$ ). Chia căn còn có những ứng dụng to lớn hơn nữa, cộng thêm việc cài đặt đơn giản, khiến cho nó trở thành một kĩ thuật vô cùng hữu ích trong phòng thi.

Tiếp nối các ứng dụng của Chia căn, trong bài viết này chúng ta sẽ cùng bàn về kĩ thuật tăng tốc độ trả lời các truy vấn bằng cách sắp xếp chúng theo một thứ tự nhất định, còn gọi là thuật toán Mo's (Mo's Algorithm).

Để làm rõ ý tưởng thuật toán, ta sẽ cùng xem xét bài toán minh họa sau:

Cho dãy số $A$ gồm $n$ phần tử $a_1, a_2, \dots, a_n$ . Với một đoạn con $[l, r]$ của dãy, ta định nghĩa $Mode(l, r)$ là giá trị xuất hiện nhiều nhất trong đoạn con đó.

Yêu cầu: Với mỗi truy vấn $(l, r)$ hãy xác định $Mode(l, r)?$

Input:

Dòng đầu tiên chứa hai số nguyên dương $n$ và $q$ - độ dài dãy số và số lượng truy vấn.
Dòng thứ hai chứa $n$ số nguyên dương $a_1, a_2, \dots, a_n$ phân tách nhau bởi dấu cách.
Trên $q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương $l, r$ thể hiện một truy vấn.

Ràng buộc:

$1 \le n, q \le 10^5$ .
$1 \le a_i \le 10^5; \forall i: 1 \le i \le n$ .

Output:

Với mỗi truy vấn, in ra kết quả trên một dòng. Nếu có nhiều giá trị thỏa mãn thì chọn giá trị nhỏ nhất.

Sample Input:

6 3
1 1 5 3 3 6
1 3
1 5
2 5

Sample Output:

1
1
3

II. Ý tưởng

Đối với bài toán trên, có thể các bạn sẽ nghĩ ngay tới Segment Tree. Tuy nhiên, nếu nhìn nhận thật kĩ thì ta thấy rằng: Khi có thông tin của hai nút con kiểm soát đoạn $[l, mid]$ và $[mid + 1, r];$ ta hoàn toàn không tạo ra được thông tin hữu ích nào cho đoạn $[l, r]$ .

Cùng xem thuật toán Mo's sẽ hoạt động hiệu quả như thế nào cho bài toán này.

1. Thuật toán ngây thơ

Cách dễ nhất là vận dụng kĩ thuật Đếm phân phối để giải quyết các truy vấn. Gọi $cnt[x]$ là số lần xuất hiện của phần tử $x;$ với mỗi truy vấn, ta sẽ tính mảng $cnt[x]$ với tất cả các giá trị $x$ thuộc đoạn $[l, r]$ :

int maxv = *max_element(a.begin() + 1, a.end());

int query(int l, int r, int maxv)
{
    int res = -1;
    vector < int > cnt(maxv + 1);
    for (int i = l; i <= r; ++i)
    {
        ++cnt[a[i]];
        
        if (res == -1 || cnt[a[i]] > cnt[res])
            res = a[i];
    }
    
    return res;
}

Thuật toán trên có độ phức tạp lên tới $O(n \times q),$ do hàm query(l, r, maxv) đã mất độ phức tạp lên tới $O(n)$ . Ta có thể cải tiến một chút vận dụng cấu trúc dữ liệu set như sau:

Khi chuyển từ truy vấn $[l_1, r_1]$ sang truy vấn $[l_2, r_2]$ thì ta thay đổi lại mảng $cnt$ một cách phù hợp:
- Nếu $l_2 > l_1$ thì ta giảm số lần xuất hiện của các giá trị $a_{l_1}, a_{l_1 + 1},..., a_{l_2 - 1}$ .
- Nếu $l_2 < l_1$ thì ta tăng số lần xuất hiện của các giá trị $a_{l_2}, a_{l_2 + 1},..., a_{l_1 - 1}$ .
- Xử lý tương tự với $r_1$ và $r_2$ .
Để tìm được phần tử nhỏ nhất có số lần xuất hiện nhiều nhất, ta vận dụng thêm cấu trúc dữ liệu set với kiểu pair < int, int >:
- Giả sử phần tử $x$ ở truy vấn $[l_1, r_1]$ có $cnt[x] = v_1$ và ở truy vấn $[l_2, r_2]$ có $cnt[x] = v_2$ .
- Ta sẽ xóa cặp giá trị $(x, v_1)$ khỏi set và thêm cặp giá trị $(x, v_2)$ vào set (viết lại hàm so sánh sắp xếp tăng các phần tử theo trường first, nếu first bằng nhau thì sắp tăng theo second).
- Phần tử xuất hiện nhiều nhất trong truy vấn $[l_2, r_2]$ sẽ là phần tử ở đầu set. Do sử dụng thêm set nên bước này tốn thêm $O(\log n)$ .
Sau khi cải tiến, thuật toán sẽ có độ phức tạp là $O\Big(\log n \times \sum_{i = 1}^q \big(|l_i - l_{i - 1}| + |r_i - r_{i - 1}|\big)\Big)$ . Rõ ràng thuật toán này không thể đáp ứng ràng buộc của bài toán.

2. Thuật toán Mo's

Sắp xếp lại các truy vấn

Ý tưởng của thuật toán Mo's trong các bài toán trả lời truy vấn đoạn là sắp xếp lại các truy vấn $[l_i, r_i]$ sao cho tổng $\sum_{i = 1}^q|l_i - l_{i - 1}| + |r_i - r_{i - 1}| \le O\big(n \times \sqrt{n} + q \times \sqrt{n}\big)$ . Hàm so sánh dưới đây sẽ thực hiện điều đó:

int block_size = ceil(sqrt(n));

bool cmp(Query a, Query b)
{
    if (a.l / block_size != b.l / block_size)
        return a.l / block_size < b.l / block_size;
    
    return a.r < b.r;
}

Cách sắp xếp này bản chất là vận dụng kĩ thuật Chia căn:

Chia dãy số $A$ thành các khối có độ dài $\text{block\_size} = \left\lceil\sqrt{n}\right\rceil$ .
Nếu đầu trái của hai truy vấn $a$ và $b$ nằm ở hai khối khác nhau thì ta sắp xếp tăng dần theo đầu trái.
Ngược lại (đầu trái của hai truy vấn thuộc cùng một khối) thì ta sắp xếp tăng dần theo đầu phải.
Thực tế, để tìm ra chỉ số khối của một vị trí $p,$ ta dùng công thức $\left\lfloor\frac{p + \text{block\_size} - 1}{\text{block\_size}}\right\rfloor$ (các khối đánh số từ $1$ ). Tuy nhiên ở đây ta chỉ cần so sánh hai đầu mút của hai truy vấn có thuộc cùng khối không nên bỏ hằng số $\text{block\_size} - 1$ đi vẫn cho ra kết quả đúng.

Tuy nhiên, do các truy vấn trong thuật toán Mo's bị sắp xếp lại, nên ta chỉ có thể áp dụng thuật toán này khi bài toán có thể xử lý offline, nghĩa là các truy vấn có thể được thực hiện lần lượt rồi mới in ra kết quả ở cuối.

Áp dụng vào việc chuyển truy vấn

Ta xây dựng mảng $s\big[v\big]$ là một mảng gồm $n$ set, set thứ $v$ lưu các giá trị $x$ có tần suất cùng là $v$ (tức là $cnt[x] = v; \forall v: 0 \le v \le n$ ). Khi chuyển truy vấn từ $[l_1, r_1]$ sang $[l_2, r_2]$ , sẽ có những $cnt[x]$ bị thay đổi (giảm đi hoặc tăng lên), đồng nghĩa với việc các $s[v]$ cũng sẽ bị thay đổi theo - do sẽ có những phần tử mới được thêm vào truy vấn $[l_2, r_2]$ nhưng cũng có những phần tử bị mất đi.

Gọi $\text{mode\_cnt}$ là chỉ số lớn nhất của mảng $s$ thỏa mãn $s[\text{mode\_cnt}] \ne \emptyset$ - đây cũng chính là số lần xuất hiện của phần tử xuất hiện nhiều nhất. Ta sẽ thiết kế hai thao tác thêm và xóa một phần tử $x$ khỏi truy vấn như sau:

Thêm một số $x$ $x$ :
- Xóa $x$ khỏi $s\big[cnt[x]\big]$ .
- Tăng $cnt[x]$ thêm $1$ .
- Thêm $x$ vào $s\big[cnt[x]\big]$ .
- Nếu như $cnt[x] > \text{mode\_cnt}$ thì cập nhật lại $\text{mode\_cnt} = cnt[x]$ và giá trị mode sẽ là phần tử đầu tiên của $s[\text{mode\_cnt}]$ .
Xóa một số $x$ $x$ :
- Xóa $x$ khỏi $s\big[cnt[x]\big]$ .
- Giảm $cnt[x]$ đi $1$ .
- Thêm $x$ vào $s\big[cnt[x]\big]$ .
- Nếu như $s[\text{mode\_cnt}]$ rỗng tức là phần tử vừa bị xóa đi chính là mode của truy vấn trước khi xóa, nên ta giảm $\text{mode\_cnt}$ đi $1$ và cập nhật lại mode của truy vấn này là phần tử đầu tiên của $s[\text{mode\_cnt}]$ .

Cuối cùng, ta tiến hành xử lý các truy vấn như sau:

Các truy vấn cần được lưu lại vị trí do đã sắp xếp theo Mo's algorithm. Gọi truy vấn thứ $i$ sau khi sắp xếp là một bản ghi $query[i],$ và vị trí chính xác của nó là $query[i].pos$ .
Gọi $res[i]$ là đáp án của truy vấn có vị trí ban đầu là $i$ . Ban đầu ta khởi tạo $res\big[query[1].pos\big]$ bằng cách gọi thao tác thêm tất cả các phần tử trong đoạn $\big[query[1].l, query[1].r\big]$ và $res\big[query[1].pos\big]$ sẽ gán bằng mode của truy vấn này.
Xét các truy vấn từ $query[2]$ $q u ery [2]$ tới $query[q],$ $q u ery [q],$ ta sẽ cập nhật kết quả cho $query[i]$ $q u ery [i]$ từ $query[i - 1]$ $q u ery [i - 1]$ như sau:
- Đặt $l_1, r_1$ là truy vấn trước. Ban đầu $l_1 = query[1].l, r_1 = query[1].r$ .
- Nếu $l_1 > query[i].l$ thì thêm các phần tử trong đoạn $\big[query[i].l, l_1 - 1\big]$ đồng thời giảm $l_1$ xuống tới khi $l_1 = query[i].l$ .
- Nếu $r_1 < query[i].r$ thì thêm các phần tử trong đoạn $\big[r_1 + 1, query[i].r\big]$ đồng thời tăng $r_1$ lên tới khi $r_1 = query[i].r$ .
- Nếu $l_1 < query[i].l$ thì xóa các phần tử trong đoạn $\big[l_1, query[i].l\big)$ đồng thời tăng $l_1$ lên tới khi $l_1 = query[i].l$ .
- Nếu $r_1 > query[i].r$ thì xóa các phần tử trong đoạn $\big[query[i].r + 1, r_1]$ đồng thời giảm $r_1$ đi tới khi $r_1 = query[i].r$ .
- Gán $res\big[query[i].pos\big] =$ mode của truy vấn hiện tại. Lưu ý thứ tự thực hiện bắt buộc phải là thêm trước - xóa sau thì thuật toán mới chính xác.

Cài đặt

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int maxn = 200010;

struct QueryType
{
    int l, r, pos;
} query[maxn];

int block_size, mode_val, mode_cnt;
int cnt[maxn], a[maxn];
set < int > s[maxn];

// Sắp xếp các truy vấn theo Mo's Algorithm.
bool cmp(QueryType a, QueryType b) 
{
    if (a.l / block_size != b.l / block_size)
        return a.l < b.l;
    else
        return a.r < b.r;
}

// Thêm 1 phần tử.
void add_value(int pos) 
{
    int val = a[pos];

    s[cnt[val]].erase(val);
    ++cnt[val];
    s[cnt[val]].insert(val);

    // nếu thêm một phần tử vào và cnt của nó > mode_cnt trước đó, thì phần tử vừa thêm vào này chính là Mode mới của
    // đoạn đang xét. Cập nhật mode mới và mode_cnt.
    if (cnt[val] > mode_cnt)
        mode_cnt = cnt[val];

    // Cập nhật giá trị mode của đoạn mới, chọn phần tử nhỏ nhất.
    mode_val = *s[mode_cnt].begin(); 
}

// Xóa 1 phần tử.
void remove_value(int pos) 
{
    int val = a[pos];

    s[cnt[val]].erase(val);
    if (cnt[val] > 0) // Nếu phần tử val đã xuất hiện rồi thì mới xóa nó đi được.
    {
        --cnt[val];
        s[cnt[val]].insert(val);
    }

    // Mode trước đó có số lần xuất hiện là mode_cnt, nếu sau bước này mà s[mode_cnt] rỗng tức là mode mới có số lần
    // xuất hiện là (mode_cnt - 1).
    if (s[mode_cnt].empty())
        --mode_cnt;

    // Cập nhật mode của đoạn mới, chọn giá trị nhỏ nhất.
    mode_val = *s[mode_cnt].begin(); 
}

void solution(int n, int t)
{
    // Sort lại các truy vấn. Tính trước truy vấn 1 và cập nhật dần lên các truy vấn sau.
    block_size = ceil(sqrt(n * 1.0));
    sort(query + 1, query + t + 1, cmp);
    
    // Khởi tạo truy vấn đầu tiên. Ban đầu tất cả các phần tử đều có tần suất là 0.
    s[0] = unordered_set < int >(a + 1, a + n + 1);
    for (int i = query[1].l; i <= query[1].r; ++i)
        add_value(i);
    
    vector < int > res(n + 1);
    res[query[1].pos] = mode_val;
    // Gọi l1, r1 là (l, r) của truy vấn trước; (l2, r2) là của truy vấn hiện tại.
    int l1 = query[1].l, r1 = query[1].r;
    for (int k = 2; k <= t; ++k)
    {
        while (l1 > query[k].l) // l1 > l2: Tăng cnt[a[l2] -> a[l1 - 1]].
        {
            --l1;
            add_value(l1);
        }
        
        while (r1 < query[k].r) // r1 < r2: Tăng cnt[a[r1 + 1] -> a[r2]].
        {
            ++r1;
            add_value(r1);
        }
        
        while (l1 < query[k].l) // l1 < l2: Giảm cnt[a[l1] -> a[l2 - 1]].
        {
            remove_value(l1);
            ++l1;
        }

        while (r1 > query[k].r) // r1 > r2: Giảm cnt[a[r2 + 1] -> a[r1]].
        {
            remove_value(r1);
            --r1;
        }

        res[query[k].pos] = mode_val;
    }

    for (int i = 1; i <= t; ++i)
        cout << res[i] << '\n';
}

main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, t;
    cin >> n >> t;

    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    for (int i = 1; i <= t; ++i)
    {
        cin >> query[i].l >> query[i].r;
        query[i].pos = i;
    }

    solution(n, t);

    return 0;
}

Đánh giá độ phức tạp

Độ phức tạp thời gian

Khi di chuyển từ $l_1$ $l_{1}$ sang $l_2$ $l_{2}$ :
- Nếu $l_1$ và $l_2$ thuộc cùng một khối: Với mỗi thao tác, do độ dài khối là $\left\lceil\sqrt{n}\right\rceil$ nên số thao tác không vượt quá $\left\lceil\sqrt{n}\right\rceil$ . Có tổng cộng $q$ truy vấn nên tổng ộộ phức tạp là $O(q \times \sqrt{n})$ .
- Nếu $l_1$ và $l_2$ thuộc hai khối khác nhau: Vì ta đã ưu tiên sắp xếp các khối theo $l$ tăng dần, nên trường hợp này xảy ra không quá $\left\lceil\sqrt{n}\right\rceil$ lần. Mỗi khi xảy ra trường hợp này tốn độ phức tạp tối đa là $O(n)$ nên độ phức tạp là $O(n \times \sqrt{n})$ .
Khi di chuyển từ $r_1$ $r_{1}$ sang $r_2$ $r_{2}$ :
- Nếu $l_1$ và $l_2$ thuộc cùng một khối: Vì trong cùng một khối, các giá trị $r$ sắp xếp tăng dần nên với mỗi khối của $l$ ta chỉ mất độ phức tạp tổng là $O(n)$ . Có tổng cộng $\left\lceil\sqrt{n}\right\rceil$ khối khác nhau nên tổng độ phức tạp là $O(n \times \sqrt{n})$ .
- Nếu $l_1$ và $l_2$ thuộc hai khối khác nhau: Do chỉ có tối đa $\left\lceil\sqrt{n}\right\rceil$ lần đổi khối và mỗi lần đổi mất tối đa $O(n)$ để di chuyển $r$ nên ta mất độ phức tạp tổng là $O(n \times \sqrt{n})$ .

Tổng hợp lại, ta có độ phức tạp thời gian $O\big((n + q) \times \sqrt{n}\big)$ .

Độ phức tạp không gian

Ta dùng tới các mảng có độ dài $n$ nên độ phức tạp không gian tổng quát là $O(n)$ .

3. Cải tiến thời gian thực thi cho Mo's Algorithm

Trên thực tế, việc đặt kích thước của các khối bằng chính xác $\left\lceil\sqrt{n}\right\rceil$ không phải luôn luôn tạo ra thời gian thực thi tối ưu. Chẳng hạn, nếu như $\left\lceil\sqrt{n}\right\rceil = 750$ thì đặt kích thước khối bằng $700$ hoặc $800$ sẽ chạy tốt hơn.

Hãy luôn luôn đặt kích thước của các khối là giá trị const, chứ không nên tính toán nó trong Runtime, bởi vì các giá trị hằng số sẽ được chương trình biên dịch tối ưu tốt hơn khi thực hiện phép chia.

Hàm sắp xếp có thể được cải tiến hơn một chút ở trường hợp chỉ số $l$ của hai truy vấn thuộc cùng một khối:

Nếu khối mang chỉ số lẻ, ta sắp xếp tăng dần đầu bên phải của truy vấn.
Nếu khối mang chỉ số chẵn, ta sắp xếp giảm dần đầu bên phải của truy vấn.
Điều này sẽ giảm thiểu chuyển động của con trỏ bên phải, vì việc sắp xếp thông thường sẽ di chuyển con trỏ bên phải từ cuối trở lại đầu ở đầu mỗi khối (do cài đặt trong thuật toán sắp xếp của STL C++). Với phiên bản cải tiến, việc khởi tạo lại này không còn cần thiết nữa.

bool cmp(QueryType a, QueryType b) // sắp xếp các truy vấn theo Mo's Algorithm.
{
    if (a.l / block_size != b.l / block_size)
        return a.l < b.l;
    else
    {
        int id = (a.l + block_size - 1) / block_size;
        return (id & 1) ? a.r < b.r : a.r > b.r;
    }
}

Thuật toán Mo's có thể được cải tiến tốc độ nhiều hơn nữa nếu sử dụng TSP và Hilbert curve. Tuy nhiên đây là kĩ thuật khó nên trong bài viết này không giới thiệu, các bạn có thể tìm đọc thêm tại đây.

III. Bài tập minh họa

1. D - Query

Đề bài

Cho dãy số $A$ gồm $n$ phần tử $a_1, a_2, \dots, a_n$ và $q$ truy vấn. Mỗi truy vấn có dạng $(l, r)$ yêu cầu bạn phải trả về số lượng phần tử phân biệt trong đoạn vị trí $[l, r]$ của dãy $A$ .

Yêu cầu: Hãy trả lời các truy vấn và đưa ra đáp án?

Input:

Dòng đầu tiên chứa số nguyên dương $n$ .
Dòng thứ hai chứa $n$ số nguyên dương $a_1, a_2, \dots, a_n$ .
Dòng thứ ba chứa số nguyên dương $q$ .
Trên $q$ dòng tiếp theo, mỗi dòng chứa một cặp số nguyên dương $l, r$ thể hiện một truy vấn.

Ràng buộc:

$1 \le n \le 30000$ .
$1 \le a_i \le 10^9; \forall i: 1 \le i \le n$ .
$1 \le q \le 2 \times 10^5$ .
$1 \le l \le r \le n$ .

Output:

Với mỗi truy vấn, in ra kết quả trên một dòng.

Sample Input:

Sample Output:

3
2
3

Ý tưởng

Đầu tiên ta sắp xếp lại các truy vấn theo Mo's Algorithm.

Để đếm số lượng phần tử phân biệt trong một truy vấn, ta sẽ duy trì mảng đếm phân phối $cnt[x]$ để đếm số lượng giá trị $x$ trong đoạn hiện tại.

Khi chuyển đoạn từ $[l_1, r_1]$ sang $[l_2, r_2],$ ta sẽ xử lý thêm - xóa phần tử theo như Mo's Algorithm, và lưu ý:

Nếu một phần tử $x$ đang có $cnt[x] = 0$ và sau khi thực hiện thao tác thêm phần tử, nó trở thành $cnt[x] = 1,$ thì số lượng phần tử phân biệt của đoạn sẽ tăng thêm $1$ .
Nếu một phần tử $x$ đang có $cnt[x] = 1$ và sau khi thực hiện thao tác xóa phần tử, nó trở thành $cnt[x] = 0,$ thì số lượng phần tử phân biệt của đoạn sẽ giảm đi $1$ .

Tuy nhiên, các giá trị $a_i \le 10^9,$ nên muốn thực hiện đếm phân phối thì phải rời rạc hóa các giá trị $a_i$ về đoạn $[1, n]$ . Các bạn có thể xem lại kĩ thuật rời rạc hóa tại đây.

Độ phức tạp: $O\big((n + q) \times \sqrt{n}\big)$ .

Cài đặt

#pragma GCC optimize("O3","unroll-loops")
#pragma GCC target("avx2")

#include <bits/stdc++.h>

using namespace std;

const int maxn = 30001, maxv = 1e6 + 1, maxq = 200001;

struct Query
{
    int l, r, pos;
} query[maxq];

int block_size;
int cnt[maxv], a[maxn];

bool cmp(Query a, Query b)
{
    if (a.l / block_size != b.l / block_size)
        return a.l < b.l;
    else
    {
        int id = (a.l + block_size - 1) / block_size;
        return (id & 1) ? a.r < b.r : a.r > b.r;
    }
}

// Rời rạc hóa mảng A về các giá trị [1...n].
void discretizing(int n)
{
    map < int, vector < int > > m;
    for (int i = 1; i <= n; ++i)
        m[a[i]].push_back(i);

    int d = 0;
    for (auto e: m)
    {
        ++d;
        for (int p: e.second)
            a[p] = d;
    }
}

// Thêm 1 phần tử.
void add_value(int pos, int& distinct_cnt)
{
    int val = a[pos];

    ++cnt[val];

    if (cnt[val] == 1)
        ++distinct_cnt;
}

// Xóa 1 phần tử.
void remove_value(int pos, int& distinct_cnt)
{
    int val = a[pos];

    if (cnt[val] > 0)
    {
        --cnt[val];

        if (cnt[val] == 0)
            --distinct_cnt;
    }
}

void solution(int n, int q)
{
    block_size = ceil(sqrt(n * 1.0));
    sort(query + 1, query + q + 1, cmp);
    discretizing(n);

    int distinct_cnt = 0;
    for (int i = query[1].l; i <= query[1].r; ++i)
        add_value(i, distinct_cnt);

    vector < int > res(q + 1);
    res[query[1].pos] = distinct_cnt;
    int l1 = query[1].l, r1 = query[1].r;
    for (int i = 2; i <= q; ++i)
    {
        while (l1 > query[i].l)
            --l1, add_value(l1, distinct_cnt);

        while (r1 < query[i].r)
            ++r1, add_value(r1, distinct_cnt);

        while (l1 < query[i].l)
            remove_value(l1, distinct_cnt), ++l1;

        while (r1 > query[i].r)
            remove_value(r1, distinct_cnt), --r1;

        res[query[i].pos] = distinct_cnt;
    }

    for (int i = 1; i <= q; ++i)
        cout << res[i] << '\n';
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    int q;
    cin >> q;

    for (int i = 1; i <= q; ++i)
        cin >> query[i].l >> query[i].r, query[i].pos = i;

    solution(n, q);

    return 0;
}

2. XOR and Favorite Number

Đề bài

Cho một mảng $A$ gồm $n$ số nguyên $a_1, a_2, \dots, a_n$ và một số nguyên $k$ .

Bạn cần trả lời $m$ truy vấn, mỗi truy vấn là một cặp số nguyên $(l, r)$ yêu cầu đếm số cặp $(i, j)$ thỏa mãn:

$l \le i \le j \le r$ .
$a_i \oplus a_{i + 1} \oplus a_{i + 2} \oplus \cdots \oplus a_r = k;$ với $\oplus$ là phép toán $\text{XOR}$ .

Yêu cầu: Hãy đưa ra đáp án của các truy vấn?

Input:

Dòng đầu tiên chứa ba số nguyên $n, m, k$ - độ dài dãy $A,$ số lượng truy vấn và số nguyên $k$ .
Dòng thứ hai chứa $n$ số nguyên dương $a_1, a_2, \dots, a_n$ .
Trên $m$ dòng tiếp theo, mỗi dòng chứa một cặp số nguyên dương $l, r$ thể hiện một truy vấn.

Ràng buộc:

$1 \le n, m \le 10^5$ .
$0 \le k \le 10^6$ .
$0 \le a_i \le 10^6; \forall i: 1 \le i \le n$ .
$1 \le l \le r \le n$ .

Output:

Với mỗi truy vấn, đưa ra đáp án trên một dòng.

Sample Input:

6 2 3
1 2 1 1 0 3
1 6
3 5

Sample Output:

7
0

Ý tưởng

Gọi $pref[i]$ là tổng $\text{XOR}$ tiền tố của các giá trị $a_{1...i}$ . Tức là:

$\begin{cases}pref[0] = 0. \\ pref[i] = pref[i - 1] \oplus a_i \end{cases}$

Khi đó, ta có tính chất tổng $\text{XOR}$ của một đoạn $a_i, a_{i + 1}, \dots, a_j$ sẽ là:

$pref[j] \oplus pref[i - 1]$

Như vậy, một truy vấn $(l, r)$ có thể đưa về bài toán đếm số cặp $(i, j)$ thỏa mãn:

$\begin{cases} l - 1 \le i < j \le r. \\ pref[j] \oplus pref[j] = k \Leftrightarrow pref[i] = k \oplus pref[j] \end{cases}$

Ta sắp xếp lại các truy vấn theo Mo's Algorithm. Thuật toán khi chuyển truy vấn sẽ như sau:

Khi thêm một phần tử $x$ (tương ứng với một $pref[j]$ hoặc một $pref[i]$ mới) vào cấu trúc dữ liệu, ta cần đếm số giá trị $y = k \oplus x$ (tương ứng với các $pref[i]$ hoặc $pref[j]$ ở trước đó) đã có sẵn, cộng thêm lượng đó vào kết quả.
Khi xóa một phần tử $x$ (tương ứng với một $pref[i]$ hoặc một $pref[j]$ bị xóa đi), ta cần đếm số giá trị $y = k \oplus x$ (tương ứng với các $pref[i]$ hoặc $pref[j]$ ở trước đó) đã có sẵn, trừ đi lượng đó khỏi kết quả.
Cả hai thao tác trên dễ dàng thực hiện bằng một mảng đếm phân phối.

Độ phức tạp: $O\big((n + q) \times \sqrt{n}\big)$ .

Cài đặt

#pragma GCC optimize("O3","unroll-loops")
#pragma GCC target("avx2")

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int maxn = 1e5 + 1, maxv = 2e6 + 1;

struct Query
{
    int l, r, pos;
} query[maxn];

int block_size;
int cnt[maxv], a[maxn], pref[maxn];

bool cmp(Query a, Query b)
{
    if (a.l / block_size != b.l / block_size)
        return a.l < b.l;
    else
        return a.r < b.r;
}

// Thêm 1 phần tử.
void add_value(int pos, int k, int& pair_cnt)
{
    int val = pref[pos];
    pair_cnt += cnt[k ^ val];
    ++cnt[val];
}

// Xóa 1 phần tử.
void remove_value(int pos, int k, int& pair_cnt)
{
    int val = pref[pos];
    --cnt[val];
    pair_cnt -= cnt[k ^ val];
}

void data_preparation(int n, int q, int k, int& pair_cnt)
{
    pref[0] = 0;
    for (int i = 1; i <= n; ++i)
        pref[i] = pref[i - 1] ^ a[i];

    block_size = ceil(sqrt(n * 1.0));
    sort(query + 1, query + q + 1, cmp);

    for (int i = query[1].l; i <= query[1].r; ++i)
        add_value(i, k, pair_cnt);
}

void solution(int n, int q, int k)
{
    int pair_cnt = 0;
    data_preparation(n, q, k, pair_cnt);

    int l1 = query[1].l, r1 = query[1].r;
    vector < int > res(q + 1);
    res[query[1].pos] = pair_cnt;
    for (int i = 2; i <= q; ++i)
    {
        while (l1 > query[i].l)
            --l1, add_value(l1, k, pair_cnt);

        while (r1 < query[i].r)
            ++r1, add_value(r1, k, pair_cnt);

        while (l1 < query[i].l)
            remove_value(l1, k, pair_cnt), ++l1;

        while (r1 > query[i].r)
            remove_value(r1, k, pair_cnt), --r1;

        res[query[i].pos] = pair_cnt;
    }

    for (int i = 1; i <= q; ++i)
        cout << res[i] << '\n';
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q, k;
    cin >> n >> q >> k;

    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    for (int i = 1; i <= q; ++i)
    {
        cin >> query[i].l >> query[i].r;
        --query[i].l;
        query[i].pos = i;
    }

    solution(n, q, k);

    return 0;
}

IV. Tài liệu tham khảo

Competitive Programming Viblo Algorithm

I. Giới thiệu chung

II. Ý tưởng

1. Thuật toán ngây thơ

2. Thuật toán Mo's

Sắp xếp lại các truy vấn

Áp dụng vào việc chuyển truy vấn

Cài đặt

Đánh giá độ phức tạp

Độ phức tạp thời gian

Độ phức tạp không gian

3. Cải tiến thời gian thực thi cho Mo's Algorithm

III. Bài tập minh họa

1. D - Query

Đề bài

Ý tưởng

Cài đặt

2. XOR and Favorite Number

Đề bài

Ý tưởng

Cài đặt

IV. Tài liệu tham khảo

Mục lục