C++ STL

IChọn container

Cách làm đúng là liệt kê thao tác trước, chọn cấu trúc sau. Bảng dưới ghi giá của các thao tác hay gặp, với $n$ là số phần tử đang chứa.

Chỉ thêm ở cuối và đọc theo chỉ số: vector. Chỉ lấy cực trị: priority_queue. Cần thứ tự (số kế tiếp, duyệt từ nhỏ đến lớn) hoặc vừa xóa bất kỳ vừa hỏi cực trị: set, multiset, map. Chỉ cần “có hay không” hoặc đếm theo khóa: bảng băm, hoặc nếu đọc hết dữ liệu trước được thì sắp rồi gom (bài 0.4), thường gọn và an toàn hơn. Hằng số cũng đáng kể, kể cả giữa các thao tác cùng $O(\log n)$:

set chậm hơn vector hơn trăm lần: mỗi phần tử là một nút cấp phát riêng và cây phải giữ cân bằng. priority_queue cũng $O(\log n)$ nhưng nằm trong một mảng liền, nên gần nhanh bằng vector.

vector là mảng nằm liền trong bộ nhớ nhưng đổi được độ dài. push_back tính trung bình chỉ tốn $O(1)$: khi hết chỗ, vector xin vùng nhớ gấp đôi rồi chép sang, và tổng số lần chép sau $n$ lần thêm là $1 + 2 + 4 + \dots < 2n$. insert và erase tại vị trí $i$ tốn $O(n - i)$ vì phải dịch phần đuôi. Hai bẫy hay gặp:

• size() trả về số không dấu: với vector rỗng, v.size() - 1 là $2^{64} - 1$, không phải $-1$.
• Xóa hàng loạt bằng erase trong vòng lặp vừa sai (nhảy qua phần tử vừa dồn về) vừa chậm $O(n^2)$. Cách đúng là v.erase(remove(v.begin(), v.end(), x), v.end()), một lượt $O(n)$.

Vài hàm có sẵn thay được vòng lặp viết tay: sort, reverse, unique (gộp phần tử bằng nhau đứng liền kề, nên sắp trước), lower_bound và upper_bound trên mảng đã sắp, max_element (trả iterator, chỉ số là hiệu với đầu mảng), accumulate, count, fill, iota. Bẫy của accumulate: kiểu kết quả là kiểu của giá trị khởi đầu, nên accumulate(a, a + n, 0) cộng trong int dù a là long long; viết 0LL.

Ví dụBao Nhiêu Giá Trị?

Đề. Dãy $n \le 2 \cdot 10^5$ số $a_i \le 10^9$. Đếm số giá trị khác nhau.

Lời giải. Hai cách cùng $O(n \log n)$: đưa mọi số vào set rồi in size(), hoặc sắp mảng rồi unique. Đọc hết dữ liệu trước được nên cách thứ hai đủ, và nhanh hơn nhiều lần vì không cấp phát nút cây nào. Giá trị tới $10^9$ nên không dùng được mảng đếm.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 2e5 + 5;
ll n, a[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (ll i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    cout << unique(a + 1, a + n + 1) - a - 1 << '\n';
}

ChạyInput8
5 2 5 7 2 9 9 1

Output5

IINgăn xếp và hàng đợi

Ba cấu trúc này chỉ cho động vào hai đầu. Ngăn xếp (stack) vào sau ra trước: push, top, pop. Hàng đợi (queue) vào trước ra trước: push ở cuối, front và pop ở đầu. Hàng đợi hai đầu (deque) cho thêm bớt ở cả hai đầu và còn truy cập d[i]. Mọi thao tác ở đầu hay cuối đều $O(1)$. Khi cần nhanh, dùng vector hay string làm ngăn xếp (push_back, back, pop_back).

top(), front(), pop() trên container rỗng không báo lỗi mà gây hành vi không xác định, nên luôn kiểm empty() trước. pop() trả về void: đọc top() rồi mới pop().

Bài quen thuộc nhất của ngăn xếp: một xâu ngoặc ()[]{} có đúng không. Quét từ trái sang, giữ ngăn xếp các ngoặc mở chưa đóng. Gặp ngoặc đóng thì ngoặc mở trong cùng, tức đỉnh, phải đúng loại; hết xâu mà ngăn xếp còn phần tử thì vẫn sai. Cùng khuôn “giữ những gì còn mở” xuất hiện ở bài phần tử gần nhất bên trái nhỏ hơn, xóa các cặp kề nhau liên tiếp. Hàng đợi là xương sống của BFS (bài 3.1).

Ví dụXóa Mẫu ABC

Đề. Xâu $S$ dài $2 \cdot 10^5$ trên bảng chữ cái A, B, C. Liên tục xóa lần xuất hiện trái nhất của ABC cho tới khi không còn, in xâu cuối.

Lời giải. Tìm lại từ đầu sau mỗi lần xóa là $O(n^2)$. Dùng ngăn xếp các ký tự giữ lại: đẩy từng ký tự vào, sau mỗi lần đẩy nếu ba ký tự trên cùng là ABC thì bỏ cả ba. Một lần xóa chỉ làm phần đứng trước nối với phần đứng sau, nên mẫu mới chỉ có thể xuất hiện ở đỉnh ngăn xếp; xóa ngay khi thấy cũng chính là xóa lần xuất hiện trái nhất. Mỗi ký tự vào ra một lần, $O(n)$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
string s, st;

signed main() {
    cin >> s;
    for (char c : s) {
        st += c;
        ll m = st.size();
        if (m >= 3 && st[m - 3] == 'A' && st[m - 2] == 'B' && st[m - 1] == 'C') st.resize(m - 3);
    }
    cout << st << '\n';
}

ChạyInputAABCABCBA

OutputABA

Lớn nhất trong mọi đoạn dài $k$. deque có một cách dùng rất hay gặp. Cho dãy $a$ và số $k$; với mỗi đoạn gồm $k$ số liền nhau, hỏi số lớn nhất trong đoạn. Đoạn này trượt dần sang phải như cửa sổ ở bài 0.7: mỗi bước thêm một số bên phải và bỏ một số bên trái. Tính lại số lớn nhất của cả đoạn mỗi bước tốn $O(k)$, cả dãy $O(nk)$, quá chậm khi $n$ và $k$ cùng lớn.

Hình dung cửa sổ là một hàng người xếp theo thứ tự tới, và ta chỉ cần biết ai cao nhất. Một người mới tới mà cao hơn mấy người đứng ngay trước mình, thì mấy người kia không bao giờ còn là người cao nhất nữa: họ thấp hơn người mới, lại rời cửa sổ sớm hơn. Cho họ về luôn.

Cứ làm vậy, hàng còn lại luôn xếp từ cao xuống thấp, và người cao nhất đứng ở đầu hàng. Khi người đứng đầu đã ra khỏi cửa sổ, cho người đó rời hàng. Cách giữ hàng này gọi là hàng đợi đơn điệu (monotonic queue): ta lưu chỉ số trong một deque, vì cần bỏ người ở cả hai đầu.

deque<ll> mx;
for (ll r = 1; r <= n; r++) {
    while (!mx.empty() && a[mx.back()] <= a[r]) mx.pop_back();
    mx.push_back(r);
    while (mx.front() <= r - k) mx.pop_front();
    if (r >= k) cout << a[mx.front()] << ' ';
}

Độ phức tạp: $O(n)$, với $n = 10^6$ cần khoảng $2 \cdot 10^6$ phép tính.

Dòng while đầu cho những người không cao hơn người mới về; push_back xếp người mới vào cuối hàng; dòng while sau bỏ người đầu hàng khi đã ra khỏi cửa sổ $[r - k + 1, r]$. Mỗi chỉ số vào hàng một lần và ra một lần, nên cả dãy là $O(n)$. Muốn số nhỏ nhất thì đổi <= thành >=.

multiset cũng làm được: thêm $a_r$, xóa một bản $a_{r-k}$, đọc phần tử cuối. Viết nhanh hơn, nhưng mỗi bước tốn $O(\log k)$ cùng một lần cấp phát nút. Đo trên một triệu số:

Hàng đợi đơn điệu nhanh hơn khoảng 18 lần. Với $n = 2 \cdot 10^5$ thì multiset vẫn qua. Khi $n$ tới $10^6$, hoặc phải chạy nhiều lần, hãy dùng deque.

IIIĐống

Một túi số, lần lượt thêm một số hoặc lấy ra số lớn nhất. Ta chỉ cần biết số lớn nhất, không cần cả túi có thứ tự; đống (heap) giữ ít thứ tự hơn nên rẻ hơn. Đống nhị phân xếp các số thành từng tầng như một cây gia phả: tầng trên cùng chỉ có một nút gọi là gốc, mỗi nút có tối đa hai nút con ở tầng ngay dưới, và các tầng được lấp đầy từ trái sang. Mỗi nút lớn hơn hoặc bằng hai con của nó, nên gốc luôn là số lớn nhất. Xếp các nút theo tầng vào mảng đánh số từ 1, nút $i$ có cha $\lfloor i/2 \rfloor$ và hai con $2i$, $2i + 1$.

Chèn: đặt số mới ở ô cuối rồi chừng nào nó lớn hơn cha thì đổi chỗ với cha. Lấy lớn nhất: chép phần tử cuối lên gốc rồi đẩy xuống, đổi chỗ với con lớn hơn chừng nào còn nhỏ hơn nó. Cây cao $\lfloor \log_2 n \rfloor$ nên cả hai là $O(\log n)$.

priority_queue là đống cài sẵn: push $O(\log n)$, top $O(1)$, pop $O(\log n)$. Mặc định nhả số lớn nhất; muốn nhả số nhỏ nhất thì khai báo priority_queue<ll, vector<ll>, greater<ll>>. Hướng so sánh ngược với sort và đó là chỗ nhiều người nhầm: priority_queue nhả phần tử sẽ đứng cuối nếu ta sắp dãy bằng chính phép so sánh đó.

Đống không có thao tác bỏ một phần tử bất kỳ. Cách chữa thông dụng là xóa lười (lazy deletion): chưa bỏ ngay, chỉ ghi nhận “phần tử này đã chết”, và dọn khi nó nổi lên đỉnh. Thuật toán Dijkstra (bài 3.5) dùng đúng cách này.

Ví dụPhiếu Giảm Một Nửa

Đề. $N \le 10^5$ món giá $A_i \le 10^9$ và $M \le 10^5$ phiếu; mỗi phiếu thay giá hiện tại $x$ của một món bằng $\lfloor x/2 \rfloor$. Dùng đủ $M$ phiếu để tổng giá nhỏ nhất.

Lời giải. Một phiếu dùng lên món giá $x$ tiết kiệm $x - \lfloor x/2 \rfloor$, lớn nhất khi $x$ lớn nhất. Và dùng phiếu lên món đắt nhất không làm hỏng các lựa chọn sau, vì mức tiết kiệm của các món khác không đổi. Vậy mỗi phiếu lấy món đang đắt nhất: max-heap, lấy đỉnh, đẩy lại $\lfloor x/2 \rfloor$. $M$ lần, mỗi lần $O(\log N)$. Tổng tới $10^{14}$, dùng long long.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n, m;
priority_queue<ll> pq;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (ll i = 1; i <= n; i++) {
        ll x;
        cin >> x;
        pq.push(x);
    }
    while (m--) {
        ll x = pq.top();
        pq.pop();
        pq.push(x / 2);
    }
    ll ans = 0;
    while (!pq.empty()) {
        ans += pq.top();
        pq.pop();
    }
    cout << ans << '\n';
}

ChạyInput4 5
20 7 3 10

Output13

IVset và hàng xóm

set giữ các khóa phân biệt luôn theo thứ tự tăng, bên trong là một cây nhị phân tìm kiếm luôn được giữ thấp, chỉ cao cỡ $\log_2 n$ tầng, nên tìm, chèn, xóa đều $O(\log n)$. Các thao tác chính: insert, erase (theo giá trị hoặc theo iterator), count, find, *s.begin() là số nhỏ nhất, *s.rbegin() là số lớn nhất, s.lower_bound(x) là phần tử đầu tiên $\ge x$, s.upper_bound(x) là phần tử đầu tiên $> x$. Iterator đi được hai chiều: next(it), prev(it).

Hai câu hỏi hàng xóm hay gặp:

• Nhỏ nhất $\ge x$: it = s.lower_bound(x), có đáp án khi it != s.end().
• Lớn nhất $\le x$: it = s.upper_bound(x), có đáp án khi it != s.begin(), và đáp án là *prev(it).

upper_bound(x) đứng ngay sau mọi phần tử $\le x$, nên phần tử liền trước nó là lớn nhất trong nhóm đó. Lấy * của end() hay lùi từ begin() là hành vi không xác định, thường hiện thành Runtime Error.

Bẫy lớn nhất là hàm lower_bound toàn cục: lower_bound(s.begin(), s.end(), x) vẫn biên dịch và cho đáp án đúng, nhưng iterator của set chỉ đi từng bước, nên nó tốn cỡ $n$ bước mỗi lần. Hàm thành viên s.lower_bound(x) đi theo cây, $O(\log n)$. Tương tự, set không biết thứ hạng của phần tử: cần phần tử nhỏ thứ $k$ khi tập còn thay đổi thì dùng cây Fenwick (bài 1.7) hay cây phân đoạn (bài 1.8).

Vmultiset và map

multiset giống set nhưng cho phép nhiều bản sao. Hai điểm khác dễ vấp:

• ms.erase(x) xóa mọi bản sao bằng $x$. Muốn xóa đúng một bản, viết ms.erase(ms.find(x)), chỉ khi chắc chắn có $x$.
• ms.count(x) tốn $O(\log n + k)$ với $k$ là số bản sao. Cần đếm nhanh thì giữ một map số lần xuất hiện.

map<K, V> là một set các cặp (khóa, giá trị) xếp theo khóa. m[k] cho tham chiếu tới giá trị của khóa $k$; nếu $k$ chưa có, nó tạo ra khóa với giá trị mặc định 0. Nhờ vậy m[x]++ đếm tần suất mà không cần kiểm gì; nhưng cũng vì vậy, chỉ đọc if (m[x] > 0) với $x$ chưa có là đã chèn thêm một khóa. Hỏi mà không chèn thì dùng m.count(x). Duyệt for (auto p : m) đi theo khóa tăng dần, với p.first là khóa, p.second là giá trị.

Ví dụVé Trong Tầm Giá

Đề. Kho có $n$ vé giá $h_i$; $m$ khách đến lần lượt, khách ngân sách $t_j$ mua vé đắt nhất có giá không vượt $t_j$ nếu có, vé đã bán bị bỏ khỏi kho. In giá vé mỗi khách mua, hoặc $-1$. $n, m \le 2 \cdot 10^5$.

Lời giải. Kho phải trả lời “số lớn nhất $\le t$” rồi xóa đúng một bản sao, và giá có thể trùng, nên dùng multiset. Với ngân sách $t$, it = upper_bound(t); nếu it == begin() thì không vé nào vừa, ngược lại lùi một bước, in và erase(it). Phải xóa theo iterator, không theo giá trị, kẻo xóa luôn các bản sao còn lại.

Độ phức tạp: cả bài $O((n + m) \log n)$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n, m;
multiset<ll> tk;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (ll i = 1; i <= n; i++) {
        ll h;
        cin >> h;
        tk.insert(h);
    }
    while (m--) {
        ll t;
        cin >> t;
        auto it = tk.upper_bound(t);
        if (it == tk.begin()) cout << -1 << '\n';
        else {
            it--;
            cout << *it << '\n';
            tk.erase(it);
        }
    }
}

ChạyInput6 5
4 8 8 3 10 6
5 8 2 10 8

Output4
8
-1
10
8

VIBảng băm

Khi chỉ cần “có hay không” hoặc đếm theo khóa mà không cần thứ tự, bảng băm (hash table) hứa $O(1)$ thay cho $O(\log n)$. Hàm băm $h$ biến khóa thành số nguyên; bảng có $B$ ô, khóa $x$ được cất ở ô $h(x) \bmod B$, mỗi ô giữ danh sách các khóa rơi vào nó. Nếu $h$ rải đều thì danh sách trung bình dưới một phần tử. Trong C++ đó là unordered_set và unordered_map, dùng giống set và map nhưng không có lower_bound, và thứ tự duyệt không xác định.

Chữ “trung bình” là điểm yếu. Với g++, hàm băm của số nguyên chính là giá trị khóa, còn số ô $B$ lấy từ một bảng số nguyên tố cố định. Biết $B$, người ra test chọn các khóa $B, 2B, 3B, \dots$: tất cả cùng dư 0 nên cùng vào ô 0, mỗi thao tác phải duyệt một chuỗi dài $n$, cả bài $O(n^2)$. Đây là kiểu hack có sẵn trên các trang thi trực tuyến.

Có ba cách tránh. Không dùng bảng băm: sắp rồi gom, hay nén tọa độ (bài 0.4). Dùng map, $O(\log n)$ không có điểm yếu nào. Hoặc tự đặt hàm băm trộn đều các bit, có hạt giống lấy từ đồng hồ để không ai dựng test trước được:

struct Hash {
    size_t operator()(ull x) const {
        static const ull seed = chrono::steady_clock::now().time_since_epoch().count();
        x += seed + 0x9e3779b97f4a7c15ULL;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
        x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
        return x ^ (x >> 31);
    }
};

Đây là hàm splitmix64: nó xáo khóa thật kỹ, hai khóa chỉ khác nhau một chút cũng cho kết quả khác hẳn, nên các bội của $B$ không còn cùng ô. Dùng như unordered_map<ll, ll, Hash>. Khóa là cặp thì ghép thành một số 64 bit trước.

Ví dụHiệu Bằng Khoảng Cách

Đề. Mảng $a_1..a_n$ với $a_i \le n$, tổng $n$ qua các test không quá $2 \cdot 10^5$. Đếm cặp $i < j$ có $a_j - a_i = j - i$.

Lời giải. Chuyển vế: $a_j - j = a_i - i$. Đặt khóa $k_i = a_i - i$, bài thành đếm cặp cùng khóa: duyệt từ trái, mỗi $j$ tạo thêm đúng cnt[k_j] cặp với các vị trí trước nó, rồi tăng đếm. Ở đây khóa chỉ nằm trong $[1 - n, n - 1]$ nên một mảng đếm có dịch chỉ số còn nhanh hơn; dùng bảng băm có hàm trộn cũng an toàn, và là cách viết khi khóa lớn tùy ý. Số cặp tới $2 \cdot 10^{10}$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
using ull = unsigned long long;

struct Hash {
    size_t operator()(ull x) const {
        static const ull seed = chrono::steady_clock::now().time_since_epoch().count();
        x += seed + 0x9e3779b97f4a7c15ULL;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
        x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
        return x ^ (x >> 31);
    }
};

ll t, n;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> t;
    while (t--) {
        cin >> n;
        unordered_map<ll, ll, Hash> cnt;
        ll ans = 0;
        for (ll i = 1; i <= n; i++) {
            ll a;
            cin >> a;
            ans += cnt[a - i]++;
        }
        cout << ans << '\n';
    }
}

ChạyInput3
5
1 2 3 4 5
5
5 4 3 2 1
6
2 3 1 4 6 5

Output10
0
3

Bảng băm được khai báo mới trong mỗi test, nên chi phí đặt lại tỉ lệ với $n$ của test chứ không phải với giới hạn lớn nhất: bài nhiều test mà đặt lại cả mảng cỡ tối đa mỗi lần là một cái bẫy thời gian quen thuộc khác.