Rời rạc hóa (nén số)

Mức độ: Cơ bản

Mảng đánh dấu cần một ô cho mỗi giá trị, nên không dùng được khi giá trị tới 10⁹. Nhưng dãy chỉ có n = 10⁵ số, tức là nhiều nhất 10⁵ giá trị khác nhau. Trong rất nhiều bài, điều quan trọng chỉ là số nào lớn hơn số nào, không phải giá trị cụ thể. Rời rạc hóa (nén số) đổi các giá trị về 1, 2, 3, … mà vẫn giữ nguyên thứ tự lớn bé, sau đó dùng mảng như bình thường.

Nén số

Dãy 1000 -7 500000000 1000 3:

1. Lấy các giá trị khác nhau rồi sắp xếp tăng dần: -7, 3, 1000, 500000000.
2. Mỗi số được thay bằng vị trí của nó trong danh sách này (đánh số từ 1).

Số ban đầu	1000	-7	500000000	1000	3
Sau khi nén	3	1	4	3	2

Số nhỏ hơn vẫn được số nhỏ hơn, hai số bằng nhau vẫn bằng nhau. Mọi câu hỏi chỉ dựa vào thứ tự (so sánh, bằng nhau, đếm) cho cùng đáp số trên dãy mới, mà dãy mới chỉ có giá trị từ 1 đến n.

Tìm vị trí của một số trong danh sách đã sắp xếp dùng tìm kiếm nhị phân: bisect_left trong Python, lower_bound trong C++, mỗi lần khoảng log₂n bước.

Python

import sys
from bisect import bisect_left
du_lieu = sys.stdin.read().split()
n = int(du_lieu[0])
a = list(map(int, du_lieu[1:1 + n]))
cac_gia_tri = sorted(set(a))                          # các giá trị khác nhau, tăng dần
nen = [bisect_left(cac_gia_tri, x) + 1 for x in a]    # vị trí, đánh số từ 1
print(*nen)

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> a(n);
    for (auto &x : a) cin >> x;
    vector<long long> cacGiaTri = a;
    sort(cacGiaTri.begin(), cacGiaTri.end());
    cacGiaTri.erase(unique(cacGiaTri.begin(), cacGiaTri.end()), cacGiaTri.end());   // bỏ số trùng
    for (int i = 0; i < n; i++) {
        int viTri = lower_bound(cacGiaTri.begin(), cacGiaTri.end(), a[i]) - cacGiaTri.begin() + 1;
        cout << viTri << (i + 1 < n ? ' ' : '\n');
    }
    return 0;
}

Cả bài mất khoảng n × log₂n bước (sắp xếp và tìm kiếm nhị phân). Trong Python, thay vì tìm kiếm nhị phân còn có thể tạo dict từ giá trị sang vị trí: vi_tri = {x: i + 1 for i, x in enumerate(cac_gia_tri)}.

Sau khi nén, đếm tần suất của giá trị lớn chỉ cần một mảng n ô: dem[nen[i]] += 1.

Đếm bằng tìm kiếm nhị phân

Trên dãy đã sắp xếp b, hai hàm tìm kiếm nhị phân cho biết:

• bisect_left(b, x) (C++ lower_bound): số phần tử nhỏ hơn x;
• bisect_right(b, x) (C++ upper_bound): số phần tử không lớn hơn x.

Từ đó trả lời được nhiều câu hỏi, mỗi câu khoảng log₂n bước:

Câu hỏi	Cách tính
có bao nhiêu số bằng x?	bisect_right(b, x) - bisect_left(b, x)
có bao nhiêu số trong đoạn từ L đến R?	bisect_right(b, R) - bisect_left(b, L)
số nhỏ nhất không nhỏ hơn x?	b[bisect_left(b, x)] (nếu vị trí đó còn trong dãy)

Dãy b = 2 4 4 4 7 9: số các số bằng 4 là 4 - 1 = 3, số các số trong đoạn từ 3 đến 8 là 5 - 1 = 4 (gồm 4, 4, 4, 7).

Đoạn thẳng trên trục số lớn: sự kiện

Có n đoạn [l, r] với tọa độ tới 10⁹, hỏi có điểm nào bị nhiều đoạn phủ nhất. Không thể làm mảng 10⁹ ô. Nhưng số đoạn phủ một điểm chỉ thay đổi ở đầu và cuối các đoạn, nên chỉ cần xét 2n vị trí đó.

Mỗi đoạn [l, r] (gồm cả hai đầu, tọa độ nguyên) tạo ra hai sự kiện:

• tại l: số đoạn đang phủ tăng 1;
• tại r + 1: số đoạn đang phủ giảm 1 (điểm r vẫn còn được phủ).

Sắp xếp các sự kiện theo tọa độ rồi đi từ trái sang phải, cộng dồn. Giá trị lớn nhất trong lúc cộng dồn là số đoạn phủ nhiều nhất. Cách này gọi là đường quét: tưởng tượng một đường thẳng quét từ trái sang phải, chỉ dừng lại ở các tọa độ có sự kiện.

Ba đoạn [1, 5], [3, 8], [6, 10]:

Tọa độ	Sự kiện	Số đoạn đang phủ
1	+1	1
3	+1	2
6	-1 (đoạn [1, 5] hết), +1	2
9	-1	1
11	-1	0

Nhiều nhất là 2 đoạn.

Python

import sys
du_lieu = sys.stdin.read().split()
n = int(du_lieu[0])
su_kien = []
for i in range(n):
    l, r = int(du_lieu[1 + 2 * i]), int(du_lieu[2 + 2 * i])
    su_kien.append((l, 1))
    su_kien.append((r + 1, -1))
su_kien.sort()          # cùng tọa độ thì -1 đứng trước +1
dang_phu = 0
nhieu_nhat = 0
for toa_do, thay_doi in su_kien:
    dang_phu += thay_doi
    nhieu_nhat = max(nhieu_nhat, dang_phu)
print(nhieu_nhat)

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<pair<long long, int>> suKien;
    for (int i = 0; i < n; i++) {
        long long l, r;
        cin >> l >> r;
        suKien.push_back({l, 1});
        suKien.push_back({r + 1, -1});
    }
    sort(suKien.begin(), suKien.end());   // cùng tọa độ thì -1 đứng trước +1
    int dangPhu = 0, nhieuNhat = 0;
    for (auto [toaDo, thayDoi] : suKien) {
        dangPhu += thayDoi;
        nhieuNhat = max(nhieuNhat, dangPhu);
    }
    cout << nhieuNhat << "\n";
    return 0;
}

Lưu ý: tại cùng một tọa độ, sự kiện -1 phải được xử lý trước sự kiện +1. Ở ví dụ trên, tại tọa độ 6 đoạn [1, 5] đã hết và đoạn [6, 10] mới bắt đầu, hai đoạn này không chung điểm nào. Nếu cộng +1 trước thì giữa chừng sẽ thấy 3 đoạn, sai. Sắp xếp cặp (tọa độ, thay đổi) tự đặt -1 trước +1 vì -1 nhỏ hơn 1.

Luyện tập

Gồm 20 bài, chia thành 4 nhóm từ dễ đến khó. Mỗi bài có một dữ liệu kiểm tra: các bạn chạy chương trình của mình với dữ liệu đó rồi so với đáp số.

Nhóm 1. Nén số và xếp hạng

Bài 1. Nén dãy số

Dòng đầu có n (1 ≤ n ≤ 10⁵), dòng thứ hai có n số nguyên (|a_i| ≤ 10⁹). Thay mỗi số bằng thứ tự của nó trong các giá trị khác nhau của dãy xếp tăng dần (số nhỏ nhất được 1). In ra dãy mới.

Ví dụ:

Nhập	In ra
5 1000 -7 500000000 1000 3	3 1 4 3 2

Kiểm tra: nhập

10
42 -1000000000 42 7 1000000000 0 7 -5 42 0

Xem đáp số

5 1 5 4 6 3 4 2 5 3

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 2. Bảng xếp hạng

Dòng đầu có n (1 ≤ n ≤ 10⁵), dòng thứ hai có điểm của n bạn theo thứ tự đăng ký (0 ≤ điểm ≤ 10⁹). Hạng của một bạn bằng 1 cộng số bạn có điểm cao hơn bạn đó (bằng điểm thì cùng hạng). In ra hạng của từng bạn theo thứ tự đăng ký.

Ví dụ:

Nhập	In ra
6 80 95 80 70 95 60	3 1 3 5 1 6

Kiểm tra: nhập

10
500 1000 0 500 750 1000 250 500 999 1

Xem đáp số

5 1 10 5 4 1 8 5 3 9

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 3. Thứ tự của các từ

Dòng đầu có n (1 ≤ n ≤ 10⁵), dòng thứ hai có n từ gồm chữ cái thường (mỗi từ dài không quá 10 chữ). Thay mỗi từ bằng thứ tự của nó trong các từ khác nhau xếp theo thứ tự từ điển (từ đứng đầu được 1). In ra dãy số mới.

Ví dụ:

Nhập	In ra
6 meo cho ga meo bo ga	4 2 3 4 1 3

Kiểm tra: nhập

10
tao tao cam le na buoi cam xoai buoi le

Xem đáp số

5 5 2 3 4 1 2 6 1 3

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 4. Cùng hình dạng

Hai dãy cùng độ dài n được gọi là cùng hình dạng nếu với mọi cặp vị trí i, j, quan hệ lớn hơn, bằng, nhỏ hơn giữa phần tử thứ i và thứ j ở hai dãy là giống nhau. Dòng đầu có n (1 ≤ n ≤ 10⁵), hai dòng sau mỗi dòng có n số nguyên (|giá trị| ≤ 10⁹). In ra YES nếu hai dãy cùng hình dạng, ngược lại in ra NO.

Ví dụ:

Nhập	In ra
5 10 30 20 30 5 2 9 7 9 -1	YES

Kiểm tra: nhập

6
4 4 8 1 6 8
100 100 300 7 200 299

Xem đáp số

NO

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 5. Số xuất hiện nhiều nhất, giá trị lớn

Dòng đầu có n (1 ≤ n ≤ 10⁵), dòng thứ hai có n số nguyên (|a_i| ≤ 10⁹). In ra số xuất hiện nhiều lần nhất và số lần đó. Nếu hòa, in số nhỏ nhất.

Ví dụ:

Nhập	In ra
7 1000000000 -3 1000000000 7 -3 -3 1000000000	-3 3

Kiểm tra: nhập

10
-999999999 5 5 123456789 -999999999 5 -999999999 0 123456789 123456789

Xem đáp số

-999999999 3

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 6. Giá trị chung của hai dãy

Dòng đầu có n, m (1 ≤ n, m ≤ 10⁵). Hai dòng sau là dãy A gồm n số và dãy B gồm m số, chưa sắp xếp, có thể trùng (|giá trị| ≤ 10⁹). In ra số giá trị khác nhau có mặt ở cả hai dãy.

Ví dụ:

Nhập	In ra
5 6 7 -2 7 100 5 5 5 3 -2 8 1000	2

Kiểm tra: nhập

8 7
1000000000 4 4 -9 0 13 -9 21
-9 13 13 999999999 0 2 21

Xem đáp số

4

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 2. Tìm kiếm nhị phân trên dãy đã sắp xếp

Bài 7. Bao nhiêu giá trị không vượt quá x

Dòng đầu có n, q (1 ≤ n, q ≤ 10⁵), dòng thứ hai có n số nguyên (|a_i| ≤ 10⁹), q dòng sau mỗi dòng có một số x. Với mỗi x, in ra trên một dòng số giá trị khác nhau của dãy không lớn hơn x.

Ví dụ:

Nhập	In ra
6 3 5 1 5 9 3 1 4 9 0	2 4 0

Kiểm tra: nhập

10 4
100 -50 100 7 7 7 2000000 -50 0 33
7
-51
1000000000
50

Xem đáp số

3
0
6
4

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 8. Đếm số trong đoạn

Dòng đầu có n, q (1 ≤ n, q ≤ 10⁵), dòng thứ hai có n số nguyên (|a_i| ≤ 10⁹), q dòng sau mỗi dòng có L, R (L ≤ R). Với mỗi câu hỏi, in ra số phần tử của dãy có giá trị từ L đến R.

Ví dụ:

Nhập	In ra
6 3 2 4 9 4 7 4 3 8 5 6 -10 100	4 0 6

Kiểm tra: nhập

10 4
15 -3 8 15 0 22 -3 8 8 1000000000
8 15
-3 -3
16 21
-1000000000 1000000000

Xem đáp số

5
2
0
10

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 9. Mỗi số xuất hiện mấy lần

Dòng đầu có n, q (1 ≤ n, q ≤ 10⁵), dòng thứ hai có n số nguyên (|a_i| ≤ 10⁹), q dòng sau mỗi dòng có một số x. Với mỗi x, in ra số lần x xuất hiện trong dãy.

Ví dụ:

Nhập	In ra
7 3 1000000000 3 3 -8 3 1000000000 0 3 1000000000 5	3 2 0

Kiểm tra: nhập

10 4
-1 -1 -1 2 2 999999999 -1 2 0 -1
-1
2
0
-2

Xem đáp số

5
3
1
0

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 10. Số gần nhất

Dòng đầu có n, q (1 ≤ n, q ≤ 10⁵), dòng thứ hai có n số nguyên (|a_i| ≤ 10⁹), q dòng sau mỗi dòng có một số x. Với mỗi x, in ra số trong dãy gần x nhất. Nếu có hai số cách x bằng nhau, in số nhỏ hơn.

Ví dụ:

Nhập	In ra
5 4 10 3 25 17 3 12 14 100 -5	10 17 25 3

Kiểm tra: nhập

8 5
-100 40 7 7 1000000000 -3 22 61
50
2
-52
500000020
31

Xem đáp số

40
-3
-100
61
22

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 11. Giá trị lớn thứ k

Dòng đầu có n, q (1 ≤ n, q ≤ 10⁵), dòng thứ hai có n số nguyên (|a_i| ≤ 10⁹), q dòng sau mỗi dòng có một số k (k ≥ 1). Với mỗi k, in ra giá trị lớn thứ k trong các giá trị khác nhau của dãy, hoặc NONE nếu dãy có ít hơn k giá trị khác nhau.

Ví dụ:

Nhập	In ra
7 3 4 9 4 1 9 7 2 1 3 6	9 4 NONE

Kiểm tra: nhập

10 4
50 -20 50 50 13 -20 999 0 13 7
2
6
7
1

Xem đáp số

50
-20
NONE
999

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 3. Đoạn thẳng trên trục số lớn

Bài 12. Tổng độ dài được phủ

Trên trục số có n đoạn [l_i, r_i] (độ dài đoạn là r_i - l_i). Dòng đầu có n (1 ≤ n ≤ 10⁵), n dòng sau mỗi dòng có l, r (0 ≤ l ≤ r ≤ 10⁹). In ra tổng độ dài phần trục số được ít nhất một đoạn phủ.

Ví dụ:

Nhập	In ra
4 1 5 3 7 10 12 11 11	8

Kiểm tra: nhập

6
100 200
0 50
150 300
40 60
1000000000 1000000000
500 600

Xem đáp số

360

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 13. Số nhóm đoạn

Hai đoạn thẳng chung ít nhất một điểm thì thuộc cùng một nhóm, và nếu đoạn A cùng nhóm với B, B cùng nhóm với C thì A cùng nhóm với C. Dòng đầu có n (1 ≤ n ≤ 10⁵), n dòng sau mỗi dòng có l, r (0 ≤ l ≤ r ≤ 10⁹) là một đoạn [l, r]. In ra số nhóm.

Ví dụ:

Nhập	In ra
5 1 3 8 9 3 5 10 12 6 7	4

Kiểm tra: nhập

7
0 0
1 1
2 10
5 20
20 25
30 1000000000
26 29

Xem đáp số

5

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 14. Khoảng trống lớn nhất

Có n cây cột điện trên một con đường thẳng, cột thứ i ở tọa độ x_i (chưa sắp xếp, có thể trùng). Dòng đầu có n (2 ≤ n ≤ 10⁵), dòng thứ hai có n số x_i (0 ≤ x_i ≤ 10⁹). In ra khoảng cách lớn nhất giữa hai cột kề nhau trên đường (giữa chúng không có cột nào khác).

Ví dụ:

Nhập	In ra
5 30 5 12 100 60	40

Kiểm tra: nhập

8
1000000000 0 500 500 250000000 999999999 3 750000000

Xem đáp số

500000000

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 15. Điểm bị phủ nhiều nhất

Dòng đầu có n (1 ≤ n ≤ 10⁵), n dòng sau mỗi dòng có l, r (0 ≤ l ≤ r ≤ 10⁹) là một đoạn [l, r] gồm cả hai đầu. In ra số đoạn nhiều nhất cùng chứa một điểm nguyên.

Ví dụ:

Nhập	In ra
3 1 5 3 8 6 10	2

Kiểm tra: nhập

6
0 1000000000
5 5
3 9
9 20
5 9
10 15

Xem đáp số

4

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 16. Số phòng khách sạn

Khách thứ i đến khách sạn vào ngày a_i và trả phòng vào ngày b_i (a_i nhỏ hơn b_i): khách ở các đêm từ ngày a_i đến trước ngày b_i. Phòng được trả vào ngày b_i dùng được cho khách đến đúng ngày đó. Dòng đầu có n (1 ≤ n ≤ 10⁵), n dòng sau mỗi dòng có a, b (1 ≤ a, b ≤ 10⁹). In ra số phòng ít nhất cần có.

Ví dụ:

Nhập	In ra
4 1 4 2 5 4 6 5 7	2

Kiểm tra: nhập

7
10 20
15 25
20 30
1 1000000000
25 26
12 13
13 15

Xem đáp số

3

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 17. Mỗi điểm thuộc mấy đoạn

Dòng đầu có n, q (1 ≤ n, q ≤ 10⁵), n dòng sau mỗi dòng có l, r (0 ≤ l ≤ r ≤ 10⁹) là một đoạn [l, r], q dòng sau mỗi dòng có một điểm x. Với mỗi x, in ra số đoạn chứa x.

Ví dụ:

Nhập	In ra
3 4 1 5 3 8 6 10 4 6 11 0	2 2 0 0

Kiểm tra: nhập

5 4
0 100
50 50
20 60
60 1000000000
99 101
50
60
100
1000000000

Xem đáp số

3
3
3
1

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 4. Vận dụng

Bài 18. Cộng đoạn, hỏi điểm

Trục số ban đầu mọi điểm nguyên đều có giá trị 0. Có m thao tác, mỗi thao tác cộng v vào mọi điểm từ l đến r. Sau đó có q câu hỏi giá trị tại điểm x. Dòng đầu có m, q (1 ≤ m, q ≤ 10⁵), m dòng sau mỗi dòng có l, r, v (0 ≤ l ≤ r ≤ 10⁹, |v| ≤ 10⁴), q dòng sau mỗi dòng có x (0 ≤ x ≤ 10⁹). In ra giá trị tại từng điểm x.

Ví dụ:

Nhập	In ra
3 4 1 5 2 3 8 10 6 6 -1 4 6 9 1	12 9 0 2

Kiểm tra: nhập

4 5
0 1000000000 1
100 200 5
150 150 -7
200 300 3
150
200
201
99
1000000000

Xem đáp số

-1
9
4
1
1

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 19. Điểm bị phủ ít nhất hai lần

Dòng đầu có n (1 ≤ n ≤ 10⁵), n dòng sau mỗi dòng có l, r (0 ≤ l ≤ r ≤ 10⁹) là một đoạn [l, r] gồm cả hai đầu. In ra số điểm nguyên nằm trong ít nhất hai đoạn.

Ví dụ:

Nhập	In ra
3 1 5 3 8 6 10	6

Kiểm tra: nhập

5
0 1000000000
10 20
15 30
1000000000 1000000000
500 500

Xem đáp số

23

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 20. Cặp điểm cùng hàng hoặc cùng cột

Có n điểm trên mặt phẳng, điểm thứ i có tọa độ (x_i, y_i), có thể có điểm trùng nhau. Dòng đầu có n (1 ≤ n ≤ 10⁵), n dòng sau mỗi dòng có x, y (|x|, |y| ≤ 10⁹). In ra số cặp điểm (không kể thứ tự) có cùng hoành độ hoặc cùng tung độ.

Ví dụ:

Nhập	In ra
5 1 1 1 5 3 1 1 1 7 7	5

Kiểm tra: nhập

8
0 0
0 1000000000
-1000000000 0
0 0
5 5
5 0
5 5
9 1000000000

Xem đáp số

12

Hướng dẫn giải chi tiết: liên hệ tác giả.

Lời giải chi tiết các bài luyện tập

Đáp số của từng bài ở ngay dưới đề để các bạn tự kiểm tra. Lời giải chi tiết (phân tích, chạy tay, chương trình Python và C++, lưu ý khi làm bài) có trong bộ tài liệu có phí của chuyên đề.

Thầy cô và các bạn muốn mua bộ tài liệu vui lòng liên hệ tác giả qua Zalo 0972465159 hoặc Facebook.