set, multiset, map có thứ tự
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úc | Thêm, xóa | Hỏi theo thứ tự |
|---|---|---|
| Mảng đã sắp xếp | dời các phần tử phía sau, tới n bước | tìm kiếm nhị phân, log n bước |
| Heap | log n bước | chỉ 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ước | log n bước |
set, multiset, map trong C++
Phần tiêu đề “set, multiset, map trong 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àm | C++ (set<int> s) | Ghi chú |
|---|---|---|
| Thêm x | s.insert(x) | |
| Xóa x | s.erase(x) | với multiset, lệnh này xóa mọi số x |
| Xóa một số x trong multiset | s.erase(s.find(x)) | phải chắc x có trong tập |
| Số nhỏ nhất ≥ x | s.lower_bound(x) | trả về s.end() nếu không có |
| Số nhỏ nhất lớn hơn x | s.upper_bound(x) | |
| Số lớn nhất ≤ x | prev(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.
Trong Python: danh sách sắp xếp và bisect
Phần tiêu đề “Trong Python: danh sách sắp xếp và bisect”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àm | Python (a là list đã sắp xếp) |
|---|---|
| Thêm x | insort(a, x) |
| Xóa một số x | a.pop(bisect_left(a, x)) |
| Vị trí số nhỏ nhất ≥ x | i = bisect_left(a, x), có khi i < len(a) |
| Vị trí số lớn nhất ≤ x | i = 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ự.
Ví dụ: số gần nhất đã xuất hiện
Phần tiêu đề “Ví dụ: số gần nhất đã xuất hiện”Đọ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.
| Đọc | Tập trước khi thêm | Liền sau | Liền trước | In ra |
|---|---|---|---|---|
| 5 | (rỗng) | |||
| 1 | 5 | 5 | không có | 4 |
| 9 | 1 5 | không có | 5 | 4 |
| 6 | 1 5 9 | 9 | 5 | 1 |
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)#include <iostream>#include <set>#include <climits>using namespace std;
int main() { int n; cin >> n; set<long long> daDoc; for (int i = 0; i < n; i++) { long long x; cin >> x; if (i > 0) { long long tot = LLONG_MAX; auto it = daDoc.lower_bound(x); // số nhỏ nhất >= x if (it != daDoc.end()) tot = *it - x; if (it != daDoc.begin()) tot = min(tot, x - *prev(it)); // số liền trước cout << tot << (i + 1 < n ? ' ' : '\n'); } daDoc.insert(x); } return 0;}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.
Lưu ý khi dùng iterator
Phần tiêu đề “Lưu ý khi dùng iterator”- Kiểm tra
it != s.end()trước khi đọc*it, vàit != s.begin()trước khi lấyprev(it). - Sau khi
erase(it)thì không dùngitnữ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. setkhông cho biết x đứng thứ mấy trong tập nhanh được (distancemất tới n bước). Câu hỏi “có bao nhiêu số nhỏ hơn x” dùng cây Fenwick.
Luyện tập
Phần tiêu đề “Luyện tập”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ố.
Nhóm 1. Thêm, xóa, tìm số gần nhất
Phần tiêu đề “Nhóm 1. Thêm, xóa, tìm số gần nhất”Bài 1. Số gần nhất đã xuất hiện
Phần tiêu đề “Bài 1. Số gần nhất đã xuất hiện”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ập | In ra |
|---|---|
45 1 9 6 | 4 4 1 |
Kiểm tra: nhập
810 3 15 7 7 -2 12 20Bài 2. Bốn thao tác trên tập
Phần tiêu đề “Bài 2. Bốn thao tác trên tập”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ập | In ra |
|---|---|
71 51 21 53 32 54 43 6 | 52-1 |
Kiểm tra: nhập
101 101 41 74 62 44 61 72 73 73 11Bà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ập | In ra |
|---|---|
51 41 91 42 42 4 | 4 44 94 94 99 9 |
Kiểm tra: nhập
81 31 -11 82 81 82 -12 32 8Bà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ập | In ra |
|---|---|
510 1 7 3 8 | 9 3 2 1 |
Kiểm tra: nhập
850 20 90 35 60 58 21 100Nhóm 2. Đoạn và chỗ trống
Phần tiêu đề “Nhóm 2. Đoạn và chỗ trống”Bài 5. Đặt lịch không trùng
Phần tiêu đề “Bài 5. Đặt lịch không trùng”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ập | In ra |
|---|---|
43 56 85 61 2 | YESYESNOYES |
Kiểm tra: nhập
710 2030 4021 2920 211 935 5041 100Bài 6. Ghế trống gần nhất
Phần tiêu đề “Bài 6. Ghế trống gần nhất”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ập | In ra |
|---|---|
5 62 2 5 2 5 1 | 2 3 5 4 -1 1 |
Kiểm tra: nhập
8 93 3 8 1 3 7 8 6 2Bài 7. Đoạn dài nhất sau mỗi lần cắt
Phần tiêu đề “Bài 7. Đoạn dài nhất sau mỗi lần cắt”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ập | In ra |
|---|---|
8 33 6 2 | 5 3 3 |
Kiểm tra: nhập
20 610 5 15 2 18 12Bà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ập | In ra |
|---|---|
41 36 72 610 10 | 3578 |
Kiểm tra: nhập
65 1020 301 411 193 25100 200Nhóm 3. Cửa sổ trượt và mô phỏng
Phần tiêu đề “Nhóm 3. Cửa sổ trượt và mô phỏng”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ập | In ra |
|---|---|
6 31 5 2 8 3 3 | 4 6 6 5 |
Kiểm tra: nhập
10 47 7 1 9 4 4 10 2 6 5Bài 10. Trung vị trên cửa sổ trượt
Phần tiêu đề “Bài 10. Trung vị trên cửa sổ trượt”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ập | In ra |
|---|---|
7 32 4 3 5 8 1 2 | 3 4 5 5 2 |
Kiểm tra: nhập
10 55 1 9 9 2 7 3 8 6 4Bài 11. Mua vé đắt nhất trong khả năng
Phần tiêu đề “Bài 11. Mua vé đắt nhất trong khả năng”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ập | In ra |
|---|---|
5 35 3 7 8 54 8 3 | 3 8 -1 |
Kiểm tra: nhập
6 710 20 20 30 5 1525 25 25 4 100 9 20Bài 12. Bảng xếp hạng theo điểm
Phần tiêu đề “Bài 12. Bảng xếp hạng theo điểm”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ập | In ra |
|---|---|
61 an 51 binh 721 an 221 chi 9 | binh 7an 7 |
Kiểm tra: nhập
91 minh 31 lan 321 minh 121 lan 41 hoa 821 hoa 2