Bỏ qua để đến nội dung

set, multiset, map có thứ tự

Mức độ: Nâng cao

Nhiều bài cho dữ liệu thay đổi liên tục (thêm số, xóa số) và hỏi những câu cần đến thứ tự: số nhỏ nhất không bé hơn x là số nào, số đứng ngay trước x là số nào, hiện giờ số lớn nhất là bao nhiêu. Các cấu trúc quen thuộc đều thiếu một thứ:

Cấu trúcThêm, xóaHỏi theo thứ tự
Mảng đã sắp xếpdời các phần tử phía sau, tới n bướctìm kiếm nhị phân, log n bước
Heaplog n bướcchỉ biết số nhỏ nhất (hoặc lớn nhất)
Bảng băm (dict, unordered_set)gần như tức thìkhông có thứ tự
set có thứ tựlog n bướclog n bước

set trong C++ là một cây tìm kiếm nhị phân tự cân bằng (giống cây AVL): các phần tử luôn được giữ theo thứ tự tăng dần, cây luôn thấp khoảng log2n tầng, nên thêm, xóa, tìm đều mất khoảng log n bước.

  • set<int>: mỗi giá trị xuất hiện một lần.
  • multiset<int>: cho phép giá trị trùng nhau.
  • map<int, int>: mỗi khóa đi kèm một giá trị, các khóa giữ theo thứ tự tăng dần.
Việc cần làmC++ (set<int> s)Ghi chú
Thêm xs.insert(x)
Xóa xs.erase(x)với multiset, lệnh này xóa mọi số x
Xóa một số x trong multisets.erase(s.find(x))phải chắc x có trong tập
Số nhỏ nhất ≥ xs.lower_bound(x)trả về s.end() nếu không có
Số nhỏ nhất lớn hơn xs.upper_bound(x)
Số lớn nhất ≤ xprev(s.upper_bound(x))chỉ dùng khi s.upper_bound(x) != s.begin()
Số nhỏ nhất, lớn nhất*s.begin(), *s.rbegin()tập phải khác rỗng

Các lệnh trả về iterator (vị trí trong cây). *it là giá trị, next(it) và prev(it) là phần tử liền sau, liền trước.

Python không có sẵn tập có thứ tự. Cách đơn giản là giữ một list luôn sắp xếp và dùng thư viện bisect:

Việc cần làmPython (a là list đã sắp xếp)
Thêm xinsort(a, x)
Xóa một số xa.pop(bisect_left(a, x))
Vị trí số nhỏ nhất ≥ xi = bisect_left(a, x), có khi i < len(a)
Vị trí số lớn nhất ≤ xi = bisect_right(a, x) - 1, có khi i >= 0

Tìm vị trí chỉ mất log n bước, nhưng thêm và xóa phải dời các phần tử phía sau, tới n bước mỗi lần. Python dời cả khối phần tử liên tiếp trong bộ nhớ nên vẫn dùng được với n khoảng 105. Khi giới hạn lớn hơn, các bạn có thể rời rạc hóa rồi dùng cây Fenwick (tìm phần tử thứ k) thay cho tập có thứ tự.

Đọc lần lượt các số. Với mỗi số x (từ số thứ hai), in khoảng cách nhỏ nhất từ x tới một số đã đọc trước đó.

Số gần x nhất chỉ có thể là số liền sau (nhỏ nhất ≥ x) hoặc số liền trước (lớn nhất nhỏ hơn x) trong tập đã đọc: mọi số khác đều xa hơn một trong hai số này. Nên mỗi số chỉ cần một lần lower_bound.

ĐọcTập trước khi thêmLiền sauLiền trướcIn ra
5(rỗng)
155không có4
91 5không có54
61 5 9951
from bisect import bisect_left, insort
def khoang_cach_gan_nhat(a, x):
"""Khoảng cách nhỏ nhất từ x tới một số trong list a đã sắp xếp (a khác rỗng)."""
i = bisect_left(a, x) # a[i] là số nhỏ nhất >= x
tot = float('inf')
if i < len(a):
tot = a[i] - x
if i > 0:
tot = min(tot, x - a[i - 1]) # a[i - 1] là số lớn nhất nhỏ hơn x
return tot
n = int(input())
so = list(map(int, input().split()))
da_doc = [so[0]]
ket_qua = []
for x in so[1:]:
ket_qua.append(khoang_cach_gan_nhat(da_doc, x))
insort(da_doc, x)
print(*ket_qua)

Cả bài mất khoảng n log n bước với C++. Thử so với mọi số đã đọc thì mất khoảng n2/2 bước.

  • Kiểm tra it != s.end() trước khi đọc *it, và it != s.begin() trước khi lấy prev(it).
  • Sau khi erase(it) thì không dùng it nữa. Cần phần tử kế tiếp thì lấy trước: it = s.erase(it) trả về phần tử liền sau.
  • set không cho biết x đứng thứ mấy trong tập nhanh được (distance mất tới n bước). Câu hỏi “có bao nhiêu số nhỏ hơn x” dùng cây Fenwick.

Gồm 12 bài, chia thành 3 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ố.

Dòng đầu có n (2 ≤ n ≤ 105), dòng thứ hai có n số nguyên a1, …, an (|ai| ≤ 109). Với mỗi i từ 2 đến n, in ra giá trị nhỏ nhất của |ai - aj| với j nhỏ hơn i.

Ví dụ:

NhậpIn ra
4
5 1 9 6
4 4 1

Kiểm tra: nhập

8
10 3 15 7 7 -2 12 20
Xem đáp số

7 5 3 0 5 2 5

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

Ban đầu tập rỗng (cho phép các số trùng nhau). Dòng đầu có q (1 ≤ q ≤ 105), q dòng sau mỗi dòng là một thao tác với 0 ≤ x ≤ 109: 1 x thêm một số x; 2 x xóa một số x (nếu không có thì bỏ qua); 3 x in số nhỏ nhất trong tập mà ≥ x; 4 x in số lớn nhất trong tập mà ≤ x. Với thao tác 3 và 4, in -1 nếu không có số nào như vậy.

Ví dụ:

NhậpIn ra
7
1 5
1 2
1 5
3 3
2 5
4 4
3 6
5
2
-1

Kiểm tra: nhập

10
1 10
1 4
1 7
4 6
2 4
4 6
1 7
2 7
3 7
3 11
Xem đáp số
4
-1
7
-1

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

Bài 3. Nhỏ nhất và lớn nhất sau mỗi thao tác

Phần tiêu đề “Bài 3. Nhỏ nhất và lớn nhất sau mỗi thao tác”

Ban đầu tập rỗng (cho phép số trùng nhau). Dòng đầu có q (1 ≤ q ≤ 105), q dòng sau mỗi dòng là 1 x (thêm một số x) hoặc 2 x (xóa một số x, đề bảo đảm x đang có trong tập), với |x| ≤ 109. Sau mỗi thao tác, in ra số nhỏ nhất và số lớn nhất của tập, hoặc EMPTY nếu tập rỗng.

Ví dụ:

NhậpIn ra
5
1 4
1 9
1 4
2 4
2 4
4 4
4 9
4 9
4 9
9 9

Kiểm tra: nhập

8
1 3
1 -1
1 8
2 8
1 8
2 -1
2 3
2 8
Xem đáp số
3 3
-1 3
-1 8
-1 3
-1 8
3 8
8 8
EMPTY

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

Bài 4. Khoảng cách nhỏ nhất sau mỗi lần thêm

Phần tiêu đề “Bài 4. Khoảng cách nhỏ nhất sau mỗi lần thêm”

Dòng đầu có n (2 ≤ n ≤ 105), dòng thứ hai có n số nguyên đôi một khác nhau (|ai| ≤ 109), được thêm lần lượt vào một tập ban đầu rỗng. Sau mỗi lần thêm (từ số thứ hai), in ra hiệu nhỏ nhất giữa hai số bất kỳ trong tập.

Ví dụ:

NhậpIn ra
5
10 1 7 3 8
9 3 2 1

Kiểm tra: nhập

8
50 20 90 35 60 58 21 100
Xem đáp số

30 30 15 10 2 1 1

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

Một phòng họp nhận lần lượt q yêu cầu (1 ≤ q ≤ 105), yêu cầu thứ i muốn dùng phòng từ thời điểm l đến thời điểm r (1 ≤ l ≤ r ≤ 109, tính cả hai đầu). Yêu cầu được nhận nếu đoạn [l, r] không có điểm chung nào với các đoạn đã nhận trước đó. Dòng đầu có q, q dòng sau mỗi dòng có l, r. Với mỗi yêu cầu, in YES nếu được nhận, NO nếu không.

Ví dụ:

NhậpIn ra
4
3 5
6 8
5 6
1 2
YES
YES
NO
YES

Kiểm tra: nhập

7
10 20
30 40
21 29
20 21
1 9
35 50
41 100
Xem đáp số
YES
YES
YES
NO
YES
NO
YES

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

Một hàng có n ghế đánh số 1 đến n, ban đầu trống. Có m người đến lần lượt, người thứ i muốn ngồi ghế xi: người đó ngồi vào ghế trống có số nhỏ nhất mà ≥ xi; nếu không còn ghế nào như vậy thì người đó ra về. Dòng đầu có n, m (1 ≤ n, m ≤ 105), dòng thứ hai có x1, …, xm (1 ≤ xi ≤ n). In ra số ghế của từng người, hoặc -1 nếu người đó ra về.

Ví dụ:

NhậpIn ra
5 6
2 2 5 2 5 1
2 3 5 4 -1 1

Kiểm tra: nhập

8 9
3 3 8 1 3 7 8 6 2
Xem đáp số

3 4 8 1 5 7 -1 6 2

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

Một thanh gỗ dài L. Lần lượt cắt n nhát tại các vị trí p1, …, pn (đo từ đầu thanh, đôi một khác nhau, 0 nhỏ hơn pi nhỏ hơn L). Dòng đầu có L, n (2 ≤ L ≤ 109, 1 ≤ n ≤ 105, n nhỏ hơn L), dòng thứ hai có p1, …, pn. Sau mỗi nhát cắt, in ra độ dài khúc gỗ dài nhất.

Ví dụ:

NhậpIn ra
8 3
3 6 2
5 3 3

Kiểm tra: nhập

20 6
10 5 15 2 18 12
Xem đáp số

10 10 5 5 5 5

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

Bài 8. Gộp đoạn và đếm điểm được phủ

Phần tiêu đề “Bài 8. Gộp đoạn và đếm điểm được phủ”

Trên trục số, lần lượt tô q đoạn (1 ≤ q ≤ 105), đoạn thứ i tô mọi điểm nguyên từ l đến r (1 ≤ l ≤ r ≤ 109). Dòng đầu có q, q dòng sau mỗi dòng có l, r. Sau mỗi lần tô, in ra số điểm nguyên đã được tô (mỗi điểm đếm một lần).

Ví dụ:

NhậpIn ra
4
1 3
6 7
2 6
10 10
3
5
7
8

Kiểm tra: nhập

6
5 10
20 30
1 4
11 19
3 25
100 200
Xem đáp số
6
17
21
30
30
131

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

Bài 9. Lớn nhất trừ nhỏ nhất trên cửa sổ

Phần tiêu đề “Bài 9. Lớn nhất trừ nhỏ nhất trên cửa sổ”

Dòng đầu có n, k (1 ≤ k ≤ n ≤ 105), dòng thứ hai có n số nguyên (|ai| ≤ 109). Với mỗi đoạn k số liên tiếp (từ trái sang phải), in ra hiệu giữa số lớn nhất và số nhỏ nhất của đoạn.

Ví dụ:

NhậpIn ra
6 3
1 5 2 8 3 3
4 6 6 5

Kiểm tra: nhập

10 4
7 7 1 9 4 4 10 2 6 5
Xem đáp số

8 8 8 6 8 8 8

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

Dòng đầu có n, k (1 ≤ k ≤ n ≤ 105, k lẻ), dòng thứ hai có n số nguyên (|ai| ≤ 109). Với mỗi đoạn k số liên tiếp, in ra trung vị của đoạn: số đứng giữa khi sắp xếp k số đó.

Ví dụ:

NhậpIn ra
7 3
2 4 3 5 8 1 2
3 4 5 5 2

Kiểm tra: nhập

10 5
5 1 9 9 2 7 3 8 6 4
Xem đáp số

5 7 7 7 6 6

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

Có n vé với giá h1, …, hn. Có m khách đến lần lượt, khách thứ j có tối đa tj đồng và mua vé đắt nhất có giá không quá tj trong số vé còn lại (vé đã bán thì không bán lại). Dòng đầu có n, m (1 ≤ n, m ≤ 105), dòng thứ hai có các giá vé, dòng thứ ba có t1, …, tm (mọi số từ 1 đến 109). In ra giá vé từng khách mua, hoặc -1 nếu khách không mua được.

Ví dụ:

NhậpIn ra
5 3
5 3 7 8 5
4 8 3
3 8 -1

Kiểm tra: nhập

6 7
10 20 20 30 5 15
25 25 25 4 100 9 20
Xem đáp số

20 20 15 -1 30 5 10

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

Một cuộc thi có q sự kiện (1 ≤ q ≤ 105). Sự kiện 1 ten d cộng thêm d điểm (1 ≤ d ≤ 1000) cho thí sinh ten (tên gồm chữ cái thường, dài không quá 10; thí sinh chưa có điểm thì coi như 0 điểm). Sự kiện 2 hỏi thí sinh đứng đầu: người có điểm cao nhất, nếu bằng điểm thì người có tên đứng trước theo thứ tự từ điển. In ra tên và điểm của người đó cho mỗi sự kiện loại 2 (đề bảo đảm đã có ít nhất một thí sinh trước sự kiện loại 2 đầu tiên).

Ví dụ:

NhậpIn ra
6
1 an 5
1 binh 7
2
1 an 2
2
1 chi 9
binh 7
an 7

Kiểm tra: nhập

9
1 minh 3
1 lan 3
2
1 minh 1
2
1 lan 4
1 hoa 8
2
1 hoa 2
Xem đáp số
lan 3
minh 4
hoa 8

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

Th.S Trần Huy Phúc

Th.S Trần Huy Phúc

Principal Software Engineer @Adnovum & Bumbii Academy