I. Giới thiệu chung

Trong lập trình thi đấu hoặc trong môn Toán, có thể các bạn đã được nghe nhiều tới khái niệm Rời rạc hóa. Ở lĩnh vực Toán học ứng dụng và Khoa học máy tính, Rời rạc hóa là quá trình chuyển các hàm, mô hình, biến hay phương trình thành các đối số rời rạc, giúp cho dữ liệu trở nên phù hợp trong việc đánh giá và thao tác trên máy tính. Bản chất của phương pháp có thể hiểu nôm na là đưa vùng dữ liệu lớn về vùng dữ liệu nhỏ để dễ xử lý hơn mà vẫn không làm thay đổi kết quả của bài toán.

Trong phạm vi chuyên đề, chúng ta sẽ nghiên cứu một kĩ thuật bổ trợ của phương pháp Rời rạc hóa là kĩ thuật Nén số, hay còn gọi là Đánh lại số thứ tự. Kĩ thuật này sẽ giúp chúng ta đưa được một dãy số từ vùng giá trị lớn về vùng giá trị nhỏ mà vẫn đảm bảo được tính tương quan lớn - nhỏ của các phần tử trong dãy số. Bài toán cơ sở có thể phát biểu như sau:

Cho dãy số $A$ gồm $n$ phần tử $a_1, a_2, \dots, a_n$. Cần đưa các giá trị trong mảng về đoạn $[1, n]$ mà vẫn đảm bảo được quan hệ lớn - bé giữa các phần tử trong mảng.

Yêu cầu: Hãy biến đổi mảng $A$ trở thành thỏa mãn điều kiện trê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 $a_1, a_2, \dots, a_n$ phân tách nhau bởi dấu cách.

Ràng buộc:

• $1 \le n \le 10^5$.
• $|a_i| \le 10^9; \forall i: 1 \le i \le n$.

Output:

• In ra mảng $A$ sau khi đã biến đổi theo yêu cầu.

Sample Input:

5
100 100 2000 1500 900000

Sample Output:

1 1 3 2 4

II. Kĩ thuật Rời rạc hóa

Để giải quyết bài toán nói trên, ta có hai cách cài đặt là Sắp xếp và Sử dụng ánh xạ (Map). Dưới đây tôi sẽ trình bày cả hai cách làm, vì chúng đều có độ phức tạp như nhau.

Cách 1: Sắp xếp

Trước tiên, ta sử dụng một mảng $B$ để lưu lại các phần tử của mảng $A$ với hai thông số:

$$b_i = \{a_i, i\}; \forall i: 1 \le i \le n$$

Tức là với mỗi giá trị $a_i$ ta sẽ lưu lại cả giá trị lẫn vị trí của nó vào mảng $B$ tương ứng.

Kế đến, sắp xếp tăng dần mảng $B$ theo giá trị $a_i$ mà nó đang lưu. Trong C++ ta có thể dễ dàng xử lý công đoạn này bằng kiểu pair, còn trong Python ta có thể sử dụng tuple. Lấy ví dụ: Với mảng $A = \{100, 100, 2000, 1500, 900000\}$ thì ta tạo được mảng $B = \big\{(100, 1), (100, 2), (1500, 4), (2000, 3), (900000, 5)\big\}$.

Kế đến, duyệt qua các phần tử của mảng $B$. Giả sử một phần tử của mảng $B$ có dạng $b_i = \{x, y\}$ thì:

• Gán $a_{b_1.y} = 1$. Nghĩa là phần tử nhỏ nhất trong mảng $A$ sẽ được gán giá trị mới là $1$.

• Tạo một biến $counter = 1$ - đây sẽ là biến lưu giá trị nén lại của các số mới. Sau đó duyệt qua các phần tử $b_i \ (2 \le i \le n),$ nếu $b_i.x \ne b_{i - 1}.x$ thì nghĩa là ta đã sang một cụm giá trị mới lớn hơn, tiến hành cập nhật:

  $$\begin{cases} counter = counter + 1 \\ a_{b_i.y} = counter\end{cases}$$

  Ngược lại nếu $b_i.x = b_{i - 1}.x$ thì tức là giá trị tương ứng trên mảng $A$ vẫn sẽ được nén lại với giá trị mới bằng $counter$. Ta cập nhật:

  $$a_{b_i.y} = counter$$

Độ phức tạp thuật toán: $O(n \times \log n)$.

Cài đặt

#include <bits/stdc++.h>

using namespace std;

void discretizing(int n, vector < int > &a, vector < pair < int, int > > &b)
{
    sort(b.begin() + 1, b.end());
    a[b[1].second] = 1;
	
    int counter = 1;
    for (int i = 2; i <= n; ++i)
        if (b[i].first != b[i - 1].first)
            a[b[i].second] = ++counter;
        else 
            a[b[i].second] = counter;
}

main()
{
    int n;
    cin >> n;
	
    vector < int > a(n + 1);
    vector < pair < int, int > > b(n + 1);
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        b[i] = {a[i], i};
    }
	
    discretizing(n, a, b);
	
    for (int i = 1; i <= n; ++i)
        cout << a[i] << ' ';
}

Cách 2: Sử dụng Ánh xạ (Map)

Ý tưởng ở đây là ta sẽ lưu lại các phần tử trong mảng $A$ với các vị trí của chúng. Tạo một map với khóa là giá trị $a_i$ và giá trị là một mảng lưu các vị trí chứa những giá trị bằng $a_i$ trong mảng $A$.

Sau đó, với một cặp $(key, value)$ trong map, ta biết rằng các vị trí xuất hiện giá trị $key$ trong mảng $A$ đang được lưu trong mảng $value$. Tạo một biến $counter$ tương tự với cách làm số $1$ và duyệt qua tất cả các vị trí xuất hiện của $key$ trong mảng $A,$ cập nhật lại toàn bộ các vị trí đó bằng $counter$.

Mỗi khi chuyển sang một cặp phần tử mới trong map thì ta tăng $counter$ lên $1$ đơn vị để chuẩn bị giá trị nén tiếp theo lớn hơn, do các phần tử trong map được sắp xếp tăng dần theo khóa.

Độ phức tạp: $O(n \times \log n)$.

#include <bits/stdc++.h>

using namespace std;

main()
{
    int n;
    cin >> n;
	
    vector < int > a(n + 1);
    map < int, vector < int > > cnt;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];    
        cnt[a[i]].push_back(i);
    }

    int counter = 0;
    for (auto e: cnt)
    {
        ++counter;
		
        for (int p: e.second)
            a[p] = counter;
    }
	
    for (int i = 1; i <= n; ++i)
        cout << a[i] << ' ';
}

III. Bài tập áp dụng

Bài 1: Phát đồng xu (HSG 12 Hà Nội 2020 - 2021)

Đề bài

Trong một trò chơi, có $n$ người chơi xếp thành một vòng tròn và được đánh số từ $1$ tới $n$ theo chiều kim đồng hồ. Trước khi trò chơi bắt đầu, sẽ có $m$ lượt phát đồng xu cho người chơi với nguyên tắc như sau: Mỗi lượt, chọn ngẫu nhiên hai số nguyên dương $l$ và $r \ (l \le n, r \le n),$ rồi phát một đồng xu cho những người chơi mang số hiệu từ $l$ tới $r$ theo chiều kim đồng hồ.

Yêu cầu: Cho trước $n, m$ và các cặp số $l, r$. Tìm số đồng xu lớn nhất mà người chơi được phát và số lượng người chơi đạt được số lượng đồng xu như vậy?

Input:

• Dòng đầu tiên chứa hai số nguyên dương $n, m$ - số lượng người chơi và số lượt phát đồng xu.
• $m$ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương $l$ và $r$ mô tả một lượt phát đồng xu.

Ràng buộc:

• $1 \le n \le 10^9$.
• $1 \le m \le 10^5$.

Subtasks:

• Subtask $1$ ($60\%$ số điểm): $1 \le n, m \le 10^3$.
• Subtask $2$ ($20\%$ số điểm): $1 \le n, m \le 10^5$.
• Subtask $3$ ($20\%$ số điểm): Không có ràng buộc gì thêm.

Output:

• Gồm hai số nguyên dương là số đồng xu lớn nhất mà người chơi được phát và số lượng người chơi đạt được số đồng xu như vậy.

Sample Input:

5 2
1 5
4 2

Sample Output:

2 4

Giải thích:

Số đồng xu của mỗi người ở mỗi lượt phát đồng xu:

• Ban đầu: $0 \ 0 \ 0 \ 0 \ 0$.
• Lượt thứ nhất: $1 \ 1 \ 1 \ 1 \ 1$.
• Lượt thứ hai: $2 \ 2 \ 1 \ 2 \ 2$.

Vậy số lượng đồng xu lớn nhất là $2$ và có $4$ người được $2$ đồng xu.

Ý tưởng

Subtask 1

Ứng với mỗi truy vấn, các bạn duyệt từng vị trí từ $l$ tới $r$ và tăng số lượng đồng xu nhận được ở các vị trí đó lên $1$ đơn vị trên một mảng. Sau đó tìm ra phần tử lớn nhất trong mảng đó và số lượng phần tử lớn nhất.

Độ phức tạp: $O(n \times m)$.

Subtask 2

Ứng với mỗi truy vấn, thay vì duyệt từ $l$ tới $r,$ thì ta áp dụng kĩ thuật update tăng đoạn kiểu "lười" trên một mảng $cnt[n + 1]$ như sau:

$$cnt[l] = cnt[l] + 1; cnt[r + 1] = cnt[r + 1] - 1$$

Riêng đối với các truy vấn cập nhật có $l > r,$ ta có thể tách làm 2 đoạn là $[l, n]$ và $[1, r]$ rồi làm theo cách trên. Các bạn có thể đọc về kĩ thuật này thêm một lần nữa tại đây.

Sau khi update xong toàn bộ các truy vấn theo cách trên, ta duyệt lại một lần các vị trí $i$ từ $1$ tới $n$ và cập nhật:

$$cnt[i] = cnt[i] + cnt[i - 1]$$

Như vậy, toàn bộ mảng $cnt$ sẽ được cập nhật chính xác. Nhiệm vụ cuối cùng ta chỉ cần đi tìm số lớn nhất trên mảng và số lượng số như vậy.

Độ phức tạp: $O\big(\text{max}(m, n)\big)$.

Subtask 3

Cách làm ở subtask 2 sẽ không thực hiện được với $n \le 10^9$ vì vừa gây tràn bộ nhớ mảng vừa không thể duyệt bằng một vòng lặp. Để cải tiến, thay vì duyệt toàn bộ các vị trí từ $1$ tới $n,$ thì ta sẽ sử dụng cấu trúc dữ liệu map để đánh số lại các đầu mút của truy vấn cập nhật tăng.

Để dễ hình dung, xét một ví dụ như sau: Giả sử ta có các truy vấn lần lượt là $[1, 5], [2, 20], [3, 10^9], [15, 10^8]$. Nếu như làm theo cách ở subtask 2 thì ta phải duyệt từ $1$ tới $10^9$ để update lại các vị trí trên mảng $cnt,$ hoàn toàn không khả thi. Thay vào đó, ta sẽ ném tất cả các đầu mút của các truy vấn cập nhật vào một mảng mới và đánh số lại chúng. Ta biết rằng, một truy vấn cập nhật $[u, v]$ thì thao tác thay đổi sẽ diễn ra ở $cnt[u]$ và $cnt[v + 1],$ vì thế ta sẽ ném hai giá trị $u$ và $v + 1$ vào một mảng mới là $pos$ rồi sắp xếp chúng lại (lưu ý lọc các giá trị trong mảng $pos$ tránh để bị trùng nhau, ví dụ hai lần đầu mút $1$ bị lặp lại). Hai mảng $pos$ và $cnt$ được mô tả như hình bên dưới, kèm theo chỉ số của các phần tử:

Và sau khi được update lại bằng một vòng lặp (giả định là ta có thể duyệt như vậy) thì trạng thái $cnt$ sẽ như thế này:

Ý nghĩa của bảng $cnt$ trên sẽ là:

• Vị trí $pos[1] = 1$ nhận được $1$ đồng xu.
• Vị trí $pos[2] = 2$ nhận được $2$ đồng xu.
• Các vị trí từ $pos[3] = 3$ tới $pos[4] - 1 = 5$ nhận được $3$ đồng xu.
• Các vị trí từ $pos[4] = 6$ tới $pos[5] - 1 = 14$ nhận được $2$ đồng xu.
• Các vị trí từ $pos[5] = 15$ tới $pos[6] - 1 = 20$ nhận được $3$ đồng xu.
• Các vị trí từ $pos[6] = 21$ tới $pos[7] - 1 = 10^8$ nhận được $2$ đồng xu.
• Các vị trí từ $pos[7] = 10^8 + 1$ tới $pos[8] - 1 = 10^9$ nhận được $1$ đồng xu.

Như vậy, với một cặp vị trí $(i, i + 1)$ trên mảng $pos$ thì rõ ràng ta biết rằng, toàn bộ những người từ vị trí $pos[i]$ tới $pos[i + 1] - 1$ đều sẽ nhận được số đồng xu cùng bằng $cnt[i],$ hoàn toàn không cần phải duyệt toàn bộ các vị trí để update lại. Vì vậy, ta chỉ cần cộng dồn từ trước ra sau trên mảng $cnt$ để có được số đồng xu ở các đoạn vị trí liên tiếp nhau, đồng nghĩa với việc ta chỉ cần update ở các vị trí tương ứng với từng cặp $(l, r)$ trên mảng $cnt$.

Vấn đề đặt ra bây giờ là, ứng với một truy vấn $(l, r)$ thì làm sao để biết $l$ và $r$ tương ứng với vị trí số mấy trên mảng $cnt?$ Cách làm là ta sử dụng map $\text{new-id}$ để đánh số lại các vị trí $l, r$ thành các $id$ tương ứng trên mảng $cnt$. Chẳng hạn, $\text{new-id}[1] = 1, \text{new-id}[6] = 4, \text{new-id}[10^8 + 1] = 7, \dots$ Sau bước này, thì với mỗi cặp $(l, r)$ ta chỉ cần tiến hành update như sau:

$$\begin{cases} cnt\big[\text{new-id}[l]\big] = cnt\big[\text{new-id}[l]\big] + 1 \\ cnt\big[\text{new-id}[r + 1]\big] = cnt\big[\text{new-id}[r + 1]\big] - 1 \end{cases}$$

Công việc còn lại chỉ là cộng dồn từ đầu tới cuối mảng $cnt$ và tiến hành xử lý tìm kết quả dựa vào các gợi ý đã cho ở trên.

Độ phức tạp: $O(m)$.

Bài 2: Dãy số

Đề bài

Cho một dãy số nguyên $A$ gồm $n$ phần tử $a_1, a_2, \dots, a_n$. Một cặp vị trí $(i, j)$ trong dãy số được gọi là cặp vị trí đặc biệt nếu như:

$$\begin{cases} i \le j \\ L \le \sum_{k = i}^j a_k \le R\end{cases}$$

Yêu cầu: Cho trước dãy số $A$ và hai số nguyên $L, R$. Hãy đếm số cặp vị trí đặc biệt trong dãy số?

Input:

• Dòng đầu tiên chứa ba số nguyên $n, L$ và $R$.
• Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \dots, a_n$ phân tách nhau bởi dấu cách.

Ràng buộc:

• $1 \le n \le 10^5$.
• $-10^9 \le L \le R \le 10^9$.
• $|a_i| \le 10^9; \forall i: 1 \le i \le n$.

Subtasks:

• Subtask $1$ ($30\%$ số điểm): $1 \le n \le 1000$.
• Subtask $2$ ($70\%$ số điểm): Không có ràng buộc gì thêm.

Output:

• In ra số cặp vị trí đặc biệt tìm được.

Sample Input:

4 2 4
1 2 3 4

Sample Output:

4

Giải thích:

Các cặp vị trí đặc biệt là: $(1, 2); (2, 2); (3, 3); (4, 4)$.

Ý tưởng

Subtask 1

Hướng làm đơn giản nhất là sử dụng hai vòng lặp, xét mọi cặp vị trí $(i, j)$ và xem tổng của đoạn đó có thỏa mãn yêu cầu của đề bài không. Mô hình thuật toán có thể mô tả như dưới đây:

int res = 0;
for (int i = 1; i <= n; ++i)
{
    int sum = 0;
    for (int j = i; j <= n; ++j)
    {
        sum += a[j];
        res += (L <= sum && sum <= R);
    }
}

Độ phức tạp cách làm này là $O(n^2),$ không thể thỏa mãn ràng buộc của bài toán.

Subtask 2

Trước tiên xây dựng mảng $sum[i]$ là tổng tiền tố của mảng $A$ từ vị trí $1$ tới vị trí $i$. Coi $sum[0] = 0$.

Nhận định rằng, một đoạn con $[j + 1, i]$ sẽ thỏa mãn yêu cầu đề bài nếu như:

$$L \le sum[i] - sum[j] \le R \Leftrightarrow sum[i] - R \le sum[j] \le sum[i] - L$$

Nói cách khác, với mỗi giá trị $sum[i]$ ta cần đếm số lượng giá trị $sum[j] \in \big[sum[i] - R, sum[i] - L\big] \ (0 \le j < i)$. Bài toán này ta có thể xử lý bằng cách dùng một Binary Indexed Tree để kiểm soát tổng số lần xuất hiện của các giá trị $sum[i], sum[i] - L$ và $sum[i] - R$.

Tuy nhiên, ta thấy rằng các giá trị $sum[i]$ có thể lên tới $|10^{14}|,$ vì vậy nếu dùng BIT lưu trực tiếp các giá trị này thì sẽ bị tràn mảng. Thay vào đó, ta sẽ nén các giá trị $sum[i], sum[i] - L$ và $sum[i] - R$ lại.

Sử dụng một mảng $s$ để lưu toàn bộ các giá trị $sum[i], sum[i] - L, sum[i] - R$ rồi sắp xếp mảng này lại và loại bỏ các phần tử trùng nhau. Rồi ứng với mỗi vị trí $i,$ ta sẽ tìm kiếm nhị phân vị trí của các giá trị $sum[i], sum[i] - L$ và $sum[i] - R$ trên mảng $s,$ dùng map để gán luôn giá trị nén của các giá trị đó bằng vị trí của chúng.

Giả sử một giá trị $sum[i]$ được nén lại bằng $z$ và hai giá trị $sum[i] - L, sum[i] - R$ được nén lại bằng $x$ và $y$. Ta sẽ cập nhật kết quả tăng thêm một lượng bằng tổng của đoạn $[x, y]$ trên BIT, rồi tăng vị trí $z$ lên $1$ đơn vị trên BIT. Cần lưu ý, muốn tính tổng đoạn $[x, y]$ thì phải lấy tổng $[1, y]$ trừ đi tổng $[1, x - 1];$ do đó để đơn giản, thay vì lưu giá trị $sum[i] - R$ thì ta sẽ lưu giá trị $sum[i] - R - 1$.

Độ phức tạp: $O(3n \times \log 3n),$ vì tối đa có thể có $3n$ giá trị số nén lại.

Cài đặt

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

using namespace std;

const int maxn = 1e5 + 10;
int sum[maxn];
int bit[3 * maxn];

// Rời rạc hóa các giá trị sum[i], sum[i] - l và sum[i] - r - 1.
void discretizing(int n, int l, int r, vector < int > &s, map < int, int > &compress)
{
    // Sắp xếp và xóa giá trị trùng lặp trong mảng s.
    sort(s.begin(), s.end());
    s.erase(unique(s.begin(), s.end()), s.end());

    for (int i = 0; i <= n; ++i)
    {
        int p0 = lower_bound(s.begin(), s.end(), sum[i]) - s.begin() + 1;
        int p1 = lower_bound(s.begin(), s.end(), sum[i] - l) - s.begin() + 1;
        int p2 = lower_bound(s.begin(), s.end(), sum[i] - r - 1) - s.begin() + 1;

        compress[sum[i]] = p0;
        compress[sum[i] - l] = p1;
        compress[sum[i] - r - 1] = p2;
    }
}

void update(int pos, int max_id)
{
    while (pos <= max_id)
    {
        ++bit[pos];
        pos += pos & -pos;
    }
}

int get_sum(int pos)
{
    int ans = 0;
    while (pos > 0)
    {
        ans += bit[pos];
        pos -= pos & -pos;
    }

    return ans;
}

// Đếm số cặp vị trí đặc biệt.
void solution(int n, int l, int r, map < int, int > &compress)
{
    int res = 0, max_id = compress.size();
    update(compress[0], max_id); // Update trước giá trị sum[0] = 0 lên cây BIT.

    for (int i = 1; i <= n; ++i)
    {
        // Tính tổng số lần xuất hiện của các giá trị [sum[i] - r, sum[i] - l] bằng 
        // cách truy vấn tổng đoạn đó trên cây BIT. Sau đó update vị trí sum[i] trên 
        // BIT tăng thêm 1 lần xuất hiện.
        res += get_sum(compress[sum[i] - l]) - get_sum(compress[sum[i] - r - 1]);
        update(compress[sum[i]], max_id);
    }

    cout << res;
}

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

    int n, l, r;
    cin >> n >> l >> r;

    vector < int > s;
    s.push_back(0); // Đưa trước giá trị sum[0] = 0 vào mảng s.
    for (int i = 1; i <= n; ++i)
    {
        int a;
        cin >> a;
        sum[i] = sum[i - 1] + a;

        // Mảng s lưu toàn bộ các giá trị sum[i], sum[i] - l và sum[i] - r - 1.
        s.push_back(sum[i]);
        s.push_back(sum[i] - l);
        s.push_back(sum[i] - r - 1);
    }

    map < int, int > compress;
    discretizing(n, l, r, s, compress);
    solution(n, l, r, compress);
	
    return 0;
}

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

• https://vnoi.info/wiki/algo/trick/Roi-rac-hoa-va-ung-dung.md.
• Competitive Programming 3 - Steven Halim & Felix Halim.