---
title
Nén số (Compression)
---

Nén số (Compression)
===

---

###### ✍️ Author: 2School Guideline
###### 📋 Content:
[TOC]

---

# Lời nói đầu

- Kĩ thuật nén số là một trong những kĩ thuật được sử dụng rất rộng rãi trong lập trình thi đấu.
- Như tên gọi, bản chất của kĩ thuật này là đưa các vùng dữ liệu lớn về vùng dữ liệu nhỏ hơn để xử lí bài toán sao cho vẫn thỏa yêu cầu của bài toán đặt ra.

# Kiến thức cần có

- Để sử dụng kĩ thuật này, trước hết ta cần phải biết:
- Thuật toán [Sắp xếp](https://hackmd.io/BmAVjN6KQkWmwzPotONuew?view&fbclid=IwAR1Vt6mJWptckoRDfr9p4zvEcc0ixuuMECiEzIDzFbKsAOr7lhmeEnNezLw)
- Thuật toán [Tìm kiếm nhị phân](https://hackmd.io/@2SchoolGuideline/SyCPwI5z6?fbclid=IwAR0yNN4NTsYzOk79uqKjHyEcAkn1qAgkG7dv-mweq4nb1uMDAno92tHd4ao#T%C3%ACm-ki%E1%BA%BFm-nh%E1%BB%8B-ph%C3%A2n-Binary-Search)

# Di chuyển đoạn tịnh tiến

- Trong C++, mảng được đánh số bắt đầu từ $0$. Tuy nhiên, có lúc các giá trị ta cần xử lí không bắt đầu từ $0$ mà bắt đầu từ con số $s$ nào đó. Lúc này nếu $s<0$ thì ta không thể truy xuất mảng, nếu $s>0$ thì khi tạo mảng, ta sẽ phí mất đoạn $[0..s]$.
- Lúc này, ta cần tìm cách để có thể tạo mảng bắt đầu từ $s$. Khi đó ta có thể tận dụng được hoàn toàn không gian mảng.

## 1. Khử số âm

- Nếu đoạn của ta bắt đầu từ số âm, ta không thể truy xuất mảng.
- Để giải quyết thì ta cộng một số **đủ lớn** để khử hết phần âm. Thường thì số này sẽ đúng bằng giá trị tuyệt đối của giới hạn số âm, hoặc số âm nhỏ nhất trong mảng.
- Ví dụ: ta biến $[-1, -2, -5, 6, 4]$ trở thành $[4, 3, 0, 11, 9]$ để có thể truy xuất, hằng số được cộng thêm là số âm nhỏ nhất.
- Trong bài [Sắp xếp](https://hackmd.io/BmAVjN6KQkWmwzPotONuew?view#4-S%E1%BA%AFp-x%E1%BA%BFp-%C4%91%E1%BA%BFm-Counting-sort), ở phần Counting sort vấn đề này đã được đề cập đến:

### 1.1. Bài toán Counting Sort

Cho một số nguyên dương $n$ và mảng $a$ gồm $n$ phần tử. Hãy sắp xếp mảng $a$ theo thứ tự **không giảm**.

#### Input

- Dòng đầu là số nguyên dương $n$ ($n \le 10^7$).
- Dòng thứ hai gồm $n$ số nguyên $a_1,a_2,...,a_n$ ($|a_i| \le 10^5$).

#### Output

- Gồm $n$ số nguyên tương ứng với mảng $a$ sau khi đã được sắp xếp.

### 1.2. Ý tưởng

- Để trình bày phương pháp này, bài viết sẽ giải bài toán trên.
- Khác với bài toán sắp xếp thông thường, hàm `sort` sẽ không thể đáp ứng được độ phức tạp thời gian.
- Nhắc lại rằng hàm `sort` có độ phức tạp trung bình là $O(n\cdot \log{n})$. Ta cần tìm thuật toán nhanh hơn độ phức tạp này.
- Tuy giới hạn của $n$ rất lớn, giới hạn của $a_i$ lại khá phù hợp để ta tận dụng ($a_i \in [-10^5..10^5]$).
- Ta sử dụng thuật toán **Counting Sort** để giải quyết vấn đề này.
- Tuy nhiên, $a$ còn bao gồm cả số âm, trong đó số âm thấp nhất có thể đạt đến $-10^5$. Để khử mất phần số âm này, ta $+10^5$ vào mỗi phần tử khi thực hiện đếm.

### 1.3. Cài đặt

#include <bits/stdc++.h>

using namespace std;

const int maxA = 1e5 + 5;

int main()
{
    int n;
    cin >> n;
    int a[n + 1];
    int cnt[2 * maxA + 1] = {0}; // maxA là phần tử lớn nhất có thể xuất hiện trong mảng, ban đầu gán tất cả cnt[i] = 0
    for (int i = 1;i <= n; ++i)
    {
        cin >> a[i];
        ++cnt[a[i]+100000]; // Tăng giá trị của cnt[a[i]] với mỗi phần tử a[i]
    }
    for (int i = 0; i <= maxA; ++i)
    {
        for (int j = 0; j < cnt[i]; ++j) cout << i-100000 << ' ';
    }
    return 0;
}

## 2. Sàng trên đoạn

### 2.1. Ý tưởng

- Ta đã biết đến thuật toán [Sàng nguyên tố Eratosthenes](https://hackmd.io/EomwVdxnT663LQaC80_Zig?view#S%C3%A0ng-nguy%C3%AAn-t%E1%BB%91) để kiểm tra tính nguyên tố của tất cả số trong khoảng $[1..N]$. Tuy nhiên, có bài toán sẽ yêu cầu tính nguyên tố của tất cả số trong khoảng $[L..R]$, trong đó $R$ rất lớn.
- Có một phương pháp gọi là **Sàng trên đoạn**, cũng sử dụng tư tưởng di chuyển đoạn để tối ưu. Điều kiện là độ dài của đoạn đó (hay $R-L+1$) phải **đủ nhỏ** cho độ phức tạp của thuật toán và để có thể tạo mảng.

### 2.2. Cài đặt

const int maxLength = 1000005;
int isprime[maxLength];

void sieve(int l, int r)
{
    // Hàm này sẽ tính toán tính nguyên tố của các số thuộc [l..r].
    // isprime[x] = true <=> x + l là số nguyên tố.
    for(int i = l; i <= r; ++i) isprime[i - l] = true;
    for(long long i = 2; i * i <= r; ++i)
    {
        // (l + i - 1) / i * i tương đương với l/i, sau đó làm tròn lên rồi nhân i, hay tương đương số đầu tiên > l là bội của i.
        for(long long j = max(i * i,(l + i - 1) / i * i); j <= r; j += i) isprime[j - l] = false;
    }
    if(1 >= l) isprime[1 - l] = false; // Trường hợp đặc biệt.
}

# Nén số theo giá trị

- Đôi khi sẽ có những bài toán yêu cầu giá trị nhập vào **rất lớn**, ta không thể tạo mảng để đếm hết giá trị trong khoảng của đề bài yêu cầu.
- Lúc này, có một giải pháp khác nếu ta thực sự cần truy xuất (như đếm) các giá trị đó. Cụ thể như sau:
- Biết rằng đề bài có thể sẽ yêu cầu nhập số lớn, nhưng chắc chắn sẽ không yêu cầu nhập vào quá nhiều số.
- Vì thế, ta sẽ **"làm nhỏ"** các số trong danh sách ban đầu bằng cách tạo ra một danh sách mới bao gồm các giá trị gọi là **giá trị nén** của số.
- Với mỗi một giá trị $x$ riêng biệt trong danh sách ban đầu, ta sẽ gọi $c(x)$ là **giá trị nén** của $x$. Mỗi một giá trị $x$ khác nhau sẽ có **duy nhất một** giá trị $c(x)$.
- Ta sẽ tìm cách làm cho $c(x)$ **nhỏ nhất có thể** để bài toán tối ưu. Nếu ta nhập vào $N$ số, ta sẽ cần **tối đa** $N$ giá trị $c(x)$ riêng biệt (trường hợp tối đa xảy ra khi không có phần tử nào trùng nhau), ta sẽ đánh dấu các số $x$ tăng dần trong mảng trở thành các giá trị $\in [1..N]$. Từ đó ta có thể truy xuất các giá trị trong độ phức tạp không gian $O(n)$ thay vì $O(maxA_i)$.

## Bài toán

#### Đề Bài

- Cho một dãy số $a$ gồm $n$ phần tử. Ta cần thực hiện $q$ truy vấn như sau:
- $x$: Đếm số lượng số có giá trị đúng bằng $x$ trong $a$.

#### Input

- Dòng $1$ gồm $2$ số nguyên $n$, $q$.
- Dòng $2$ gồm $n$ số nguyên $a_1,a_2,...a_n$.
- $q$ dòng tiếp theo gồm $1$ số $x$.

#### Output

- In ra $q$ dòng là kết quả của $q$ truy vấn.

#### Giới hạn
- $1 \le n, q \le 2\cdot10^5$
- $|a_i| \le 10^9$

#### Sample Input

8 5
-5 2 3 2 2 3 1 1000000000
1 
2
3
-3
998244353

#### Sample Output

1
3
2
0
0

#### Giải thích

- Truy vấn thứ $1$: có $1$ số $1$ trong $a$.
- Truy vấn thứ $2$: có $2$ số $3$ trong $a$.
...

### Ý tưởng

- Vì có nhiều truy vấn, ta không thể duyệt qua $a$ ở từng truy vấn để đếm. Ta **cần** một bước tiền xử lí để tạo ra một mảng $cnt_x$ là số giá trị $x$ có trong $a$.
- Nhận thấy rằng ta **không thể** tạo mảng $2\cdot10^9$ phần tử cho từng số trong khoảng đó. Thậm chí mảng còn **có cả số âm** sẽ rất phức tạp.
- Ta áp dụng thuật toán từ nhận xét ở trên để thực hiện tiền xử lí:
- Với mỗi giá trị $a_i$ **riêng biệt** có trong $a$, ta lần lượt định nghĩa $c(a_i) =$ số lượng **số khác nhau** trước nó.
- Thứ tự của $a_i$ so với $c(a_i)$ là **không quan trọng**. Vậy nên để tối ưu thì trước tiên ta có thể sắp xếp $a$. Nếu cần giữ lại mảng $a$ cho các mục đích khác, ta có thể tạo ra 1 mảng $b$ và dùng nó làm mảng nén.
- Tương tự với bài [CSES - Distinct Numbers](https://cses.fi/problemset/task/1621) đã được trình bày rất rõ ở bài tập của chủ đề [Sắp xếp](https://hackmd.io/BmAVjN6KQkWmwzPotONuew?view), ta có một cách thực hiện hóa ý tưởng này là **sắp xếp** $a$ lại và **xóa** các **phần tử trùng nhau**. Sau đó có thể sử dụng luôn chỉ số của mỗi phần tử làm giá trị nén.
- **Lưu ý:** Tránh để bị quá thời gian ở bước nén.
- Với tối đa $n$ số trong mảng, hiển nhiên $\forall c(a_i) \in [1..N]$.
- Từ đó ta có thể tạo mảng để đếm các giá trị trên.
- Để đơn giản hơn khi truy xuất thì trước hết ta sẽ sắp xếp $a$ không giảm, khi đó giá trị nén cũng sẽ đồng biến với giá trị ban đầu.
- Một cách để cài đặt là tạo ra một tập hợp $s$ chứa tất cả phần tử của $a$, sau đó trực tiếp sử dụng chỉ số của phần tử trong tập hợp làm giá trị nén.
- Ngoài ra, ta cũng có thể sử dụng CTDL `std::map` để đếm. Nhưng bản chất của nó cũng chính là kĩ thuật nén số.

### Cài đặt

- Sử dụng `v.erase(unique(v.begin(), v.end()), v.end())` và thuật toán tìm kiếm nhị phân để nén giá trị theo chỉ số khi đưa $a$ thành tập hợp.
- Hàm này có độ phức tạp thời gian là $O(n)$, hoàn toàn an toàn trong bước này.
- Lưu ý: **Cần phải sắp xếp trước khi** thực hiện `v.erase(unique(v.begin(), v.end()), v.end())`.

#include <bits/stdc++.h>

using namespace std;

const int maxn = 200005;

int a[maxn], cnt[maxn];

int main()
{
    int n, q;
    cin >> n >> q;
    vector<int> a(n), s(n);
    for(int i = 0; i < n; ++i) cin >> a[i];

    s = a; // s là tập hợp của a
    sort(s.begin(), s.end());
    s.erase(unique(s.begin(), s.end()), s.end());
    for(int i = 0; i < n; ++i)
    {
        int cs = lower_bound(s.begin(), s.end(), a[i]) - s.begin();
        cnt[cs]++; // Sử dụng tìm kiếm nhị phân để tìm chỉ số
    }

    while(q--)
    {
        int x;
        cin >> x;
        if((s.back() < x) || (*lower_bound(s.begin(), s.end(), x) != x)) cout << 0 << '\n'; // Xử lí trường hợp nếu x không nằm trong tập hợp
        else
        {
            int cs = lower_bound(s.begin(), s.end(), x) - s.begin();
            cout << cnt[cs] << '\n';
        }
    }
    return 0;
}

# Bài tập
## [CSES - Restaurant Customers](https://cses.fi/problemset/task/1619)
### Đề bài
- Cho biết thời gian đến và rời đi của khách hàng của 1 nhà hàng. Hãy cho biết số lượng khách hàng lớn nhất tại nhà hàng vào 1 thời điểm bất kì
### Input
- Dòng đầu tiên có 1 số nguyên $n$: số lượng khách hàng
- $n$ dòng tiếp theo, mỗi dòng gồm hai số nguyên $a, b$ cho biết thời gian đến và rời đi của khách hàng đó (nghĩa là người đó sẽ ở trong nhà hàng trong khoảng thời gian $[a, b]$)
### Output
- In ra 1 số nguyên: số lượng khách hàng lớn nhất
### Giới hạn
- $1 \le n \le 2 \cdot 10^5$
- $1 \le a < b \le 10^9$
### Sample testcase
#### Input

3
5 8
2 4
3 9

#### Output

2

### Giải thích
- $k = 1:$ $0$ người
- $k = 2:$ $1$ người
- $k = [3, 8]:$ $2$ người
- $k = 9:$ $1$ người

### Lời giải
:::spoiler **Hướng dẫn giải**
- Với bài tập này, ta sẽ được cho nhiều đoạn và ta cần tính xem giá trị lớn nhất các đoạn chồng lên nhau ở 1 vị trí bất kì là bao nhiêu
- Với bài này ta có thể áp dụng kĩ thuật dùng [mảng hiệu](https://hackmd.io/aKhTQV8gRU-JCS4isaiYkQ#Mảng-hiệu) đã được nhắc đến ở bài viết trước đây của 2SG.
- Thao tác nén ở đây chính là thao tác sort lại mảng theo thứ tự tăng dần đối với thời gian ra vào của khách hàng. Thế nhưng ta không cần nén trực tiếp ra thành các giá trị khác mà chỉ ngầm hiểu rằng nó đã được nén, vì ta không cần thiết dùng đến thời gian của khách hàng.
- Thế nhưng các bạn vẫn có thể thử nén các giá trị đó ra thành 1 mảng và thực hiện y như các bước được nhắc ở trên để có thể làm quen với kĩ thuật này
:::

:::spoiler **Code mẫu**

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

int main()
{
	cin.tie(nullptr)->sync_with_stdio(false);
	int n; cin >> n;
	vector <pair<int, int>> times;
	for (int i = 1; i <= n; ++i)
	{
		int l, r; cin >> l >> r;
		times.push_back({l, 1});
		times.push_back({r+1, -1});
	}
	sort(times.begin(), times.end());

	// Cách có nén mảng 
	int ind = 0;
	vector <int> ppl_change(2*n+1);
	for (int i = 0; i < (int)times.size(); ++i)
	{
		ppl_change[ind] = times[i].second;
		ind++;
	}
	int ans = 1;
	for (int i = 1; i < 2*n; ++i)
	{
		ppl_change[i] += ppl_change[i-1];
		ans = max(ans, ppl_change[i]);
	}
	// Cách không nén mảng
	int ans = 0, curr = 0; // curr biểu thị số khách hàng đang trong cửa hàng hiện tại
	for (int i = 0; i < (int)times.size(); ++i)
	{
		curr += times[i].second;
		ans = max(ans, curr);
	}
	// //
	cout << ans << endl;
	// return 0;
}

:::