# **C++ STL**
C++ STL là một thư viện template cho C++ với những cấu trúc dữ liệu cũng như giải thuật được xây dựng tổng quát mà vẫn tận dụng được hiệu năng và tốc độ của C. Thư viện STL giúp người dùng thực hiện toàn bộ các công việc như vào ra dữ liệu, quản lý mảng động, xây dựng sẵn những cấu trúc dữ liệu cơ bản và bao gồm cả các giải thuật cơ bản như sắp xếp, tìm min - max, tính tổng, thậm chí là tìm ước chung lớn nhất chẳng hạn. Việc sử dụng STL là rất quan trọng đối với những bạn nào có định hướng tham gia những kỳ thi HSG Tin học.

**Để sử dụng thư viện STL, ta chỉ cần khai báo:**```#include <bits/stdc++.h>```

# 1. Map
Mỗi phần tử của map là sự kết hợp của khóa (key) và ánh xạ của nó (value). Trong map không chứa các khóa mang giá trị giống nhau. Các khóa được sử dụng để xác định giá trị các phần tử. Kiểu của khóa và ánh xạ có thể khác nhau. Các phần tử trong map được sắp xếp theo trình tự nào đó theo cách so sánh (mặc định là theo trình tự tăng dần).

**Khai báo:**

map<kiểu_dữ_liệu_1, kiểu_dữ_liệu_2> tên_map
//với kiểu dữ liệu 1 là key, kiểu dữ liệu 2 là value

Ví dụ: $map<int, int> mp$;
**Cách truy cập phần tử trong map:** $mp[x]$ (truy cập phần tử có khóa là $x$): Nếu khóa đã có trong map thì trả về giá trị của khóa. Ngược lại, nó sẽ thêm khóa đó vào map với giá trị 0. Độ phức tạp: $O(logN)$. Ta có thể thêm phần tử vào map bằng cú pháp sau: $mp[x] = v$ (thêm khóa $x$ với giá trị $v$ vào map) với độ phức tạp $O(logN)$.
***Ta có thể truy cập vào từng phần tử của map bằng cách dưới đây:***

map<int,int> mp;
for (auto x : mp) {
    cout << x.first << ' ' << x.second << '\n';
    // với x.first là khóa và x.second là ánh xạ.
}

**Các hàm hay dùng với map:**
- size: trả về kích thước hiện tại của map. Độ phức tạp: $O(1)$. Cú pháp: $mp.size()$.
- empty: trả về true nếu map rỗng, ngược lại trả về false. Độ phức tạp: $O(1)$. Cú pháp: $mp.empty()$.
- insert: chèn phần tử vào map (phần tử phải là kiểu pair). Độ phức tạp: $O(logN)$. Cú pháp: $mp.insert(x)$ (thêm phần tử x vào map).
- erase: xóa phần tử trong map. Độ phức tạp: $O(logN)$. Cú pháp: $mp.erase(x)$ (xóa phần tử x ra khỏi map).
- clear: xóa toàn bộ phần tử trong map. Độ phức tạp: $O(N)$. Cú pháp: $mp.clear()$.
- find: trả về iterator trỏ đến phần tử cần tìm kiếm. Nếu không tìm thấy iterator trỏ về “end” của map. Độ phức tạp: $O(logN)$. Cú pháp: $mp.find(x)$ (tìm phần tử có khóa x).

**unordered_map:**

unordered_map là 1 map nhưng với các phần tử không được sắp xếp theo khóa. Cách khai báo và các hàm tương tự với map. So sánh độ phức tạp các thao tác của map và unordered_map:

| Thao tác | map | unordered_map |
| -------- | ------- | ------------------------------------------- |
| Thêm và xóa phần tử | $O(logN)$ | trung bình: $O(1)$, trường hợp tệ nhất: $O(n)$. |
| Tìm kiếm | $O(logN)$ | trung bình: $O(1)$, trường hợp tệ nhất: $O(n)$. |

***-> Ta nên dùng unordered_map khi không sử dụng đến tính chất sắp xếp của map, ngược lại hãy sử dụng map***.

**So sánh map và mảng đánh dấu:**
Ta có thể sử dụng map để đánh dấu thay cho mảng thông thường tùy thuộc vào yêu cầu của đề bài. So sánh giữa sử dụng map và sử dụng mảng:

| | Mảng | Map |
| -------- | -------- | -------- |
| Độ phức tạp cập nhật | $O(1)$ | $O(logN)$
| Giới hạn của số cần đánh dấu | $10^{7}$ | $10^{18}$
| Đánh dấu được các kiểu dữ liệu khác | Không | Có

Ta có ví dụ nhỏ như sau:

Cho mảng $a$ gồm $n$ phần tử. In ra số lần xuất hiện của từng phần tử trong $a$ theo chỉ số tăng dần.
**Input:**
- Dòng đầu tiên ghi $n$ với $n$ là số phần tử của mảng $a$ ($n$≤$10^{5}$, $a_{i}$ ≤$10^{9}$).
- Dòng tiếp theo ghi $n$ số nguyên dương lần lượt là các giá trị từ $a_{1}$, $a_{2}$, $a_{3}$, ..., $a_{n}$.

**Output:**
- Một dòng duy nhất in ra số lần xuất hiện của từng phần tử trong $a$ theo chỉ số tăng dần.

**Sample Input:**

6
1 5 0 2 2 0

**Sample Output:**

1 1 2 2 2 2

**Phân tích:**
- Vì giới hạn của các số trong mảng là $10^{9}$ nên chúng ta không thể đánh dấu bằng mảng mà phải sử dụng map. Bài toán này không cần sử dụng đến tính chất sắp xếp nên ta có thể dùng unordered_map thay cho map để tối ưu độ phức tạp.

**Code mẫu:**

#include <bits/stdc++.h>
using namespace std;
const int mx = 1e6 + 5;
const int mod = 1e9 + 7;
int n, a[mx];
signed main() {
	cin >> n;
	unordered_map<int,int> mp;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		mp[a[i]]++;
	}
	for (int i = 1; i <= n; i++) {
		cout << mp[a[i]] << ' ';
	}
	return 0;
}
//honguwu	

***Ánh xạ dãy số (nén số) bằng map***:
Ta có thể sử dụng map để ánh xạ dãy số. Ánh xạ dãy số được thực hiện như sau: Giả sử ta nén số một mảng $A_{i}$ có $n$ phần tử có giá trị thuộc khoảng [$−10^{9}$,$10^{9}$] về mảng nhỏ hơn có giá trị thuộc khoảng [1,$n$] mà vẫn đảm bao được quan hệ lớn bé. Ví dụ: $a$ = {100, 100, 2000, 1500, 900000} → $b$ = {1,1,3,2,4}.
**Code mẫu:**

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

#define pii pair<int, int>

const int N = 1e6 + 5;

int a[N], b[N], c[N];
map<int, int> mp;

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n; cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        mp[a[i]]++;
    }
    int cnt = 0;
    for (auto it : mp) {
        cnt++;
        b[cnt] = it.first;
    }
    for (int i = 1; i <= n; i++) {
        int x = lower_bound(b + 1, b + 1 + cnt, a[i]) - b;
        c[i] = x;
    }
}
// mảng c chứa dãy số sau khi được ánh xạ.

# 2. Set
Set là lưu trữ các phần tử không bị trùng lặp (unique elements), và các phần tử này chính là các khóa (keys). Các phần tử của set sẽ tăng dần theo phép toán so sánh (mặc định là tăng dần). Bạn cũng có thể viết lại hàm so sánh theo ý của mình.
**Khai báo:**
- Dạng 1 (sử dụng phép toán mặc định): ```set<kiểu_dữ_liệu> s;``` (sắp xếp tăng dần)
- Dạng 2 (sử dụng phép toán khác): ```set<kiểu_dữ_liệu, greater<kiểu_dữ_liệu>> s //phép toán greater;``` (sắp xếp giảm dần).

Phép toán khác cũng có thể do người dùng tự định nghĩa. Ví dụ cách khai báo ở dạng 2 tương đương với:

struct cmp{
 bool operator() (int a,int b) {return a>b;}
};
set <int,cmp> s ;

***Ta có thể truy cập vào từng phần tử của set bằng cách dưới đây:***

set<int> s;
for (auto x : s) {
    cout << x << ' ';
}

**Ta cũng có thể truy cập phần tử đầu tiên và cuối cùng của set bằng cách:**

cout << *s.begin(); // phần tử đầu tiên
cout << *s.rbegin(); // phần tử cuối cùng

**Các hàm hay dùng với set:**
- size: trả về kích thước hiện tại của set. Độ phức tạp: $O(1)$. Cú pháp: $s.size()$.
- empty: trả về true nếu set rỗng, ngược lại trả về false. Độ phức tạp: $O(1)$. Cú pháp: $s.empty()$.
- insert: chèn phần tử vào set. Độ phức tạp: $O(logN)$. Cú pháp: $s.insert(x)$ (thêm phần tử x vào set).
- erase: xóa phần tử trong set. Độ phức tạp: $O(logN)$. Cú pháp: $s.erase(x)$ (xóa phần tử x ra khỏi set).
- clear: xóa toàn bộ phần tử trong set. Độ phức tạp: $O(N)$. Cú pháp: $s.clear()$.
- find: trả về iterator trỏ đến phần tử cần tìm kiếm. Nếu không tìm thấy iterator trỏ về “end” của set. Độ phức tạp: $O(logN)$. Cú pháp: $s.find(x)$ (tìm phần tử có khóa x).
- lower_bound : trả về iterator đến vị trí phần tử bé nhất mà lớn hơn hoặc bằng khóa theo phép so sánh, nếu không tìm thấy trả về vị trí “end” của set. Độ phức tạp: $O(logN)$. Cú pháp: s.lower_bound(x).
- upper_bound : trả về iterator đến vị trí phần tử bé nhất mà lớn hơn khóa theo phép so sánh, nếu không tìm thấy trả về vị trí “end” của set. Độ phức tạp: $O(logN)$. Cú pháp: s.upper_bound(x).

***Cách dùng lower_bound và upper_bound để tìm phần tử đầu tiên lớn hơn hoặc bằng $x$ và lớn hơn $x$ trong set:***

cout << *s.lower_bound(x); // tìm phần tử đầu tiên lớn hơn hoặc bằng x
cout << *s.upper_bound(x); // tìm phần tử đầu tiên lớn hơn x

**Khai báo iterator trong set:**

set<int> :: iterator it;

**Multiset:**
Multiset giống như set nhưng có thể *chứa các giá trị giống nhau*. Cách khai báo và các hàm tương tự như set.
# 3. Priority Queue
Priority queue được thiết kế đặc biệt để phần tử ở đầu luôn luôn lớn nhất (theo một quy ước về độ ưu tiên nào đó), phần tử có độ ưu tiên lớn nhất có thể được lấy ra và các phần tử khác được chèn vào bất kì. Phép toán so sánh mặc định khi sử dụng priority queue là phép toán less (phần tử lớn nhất được lấy ra đầu tiên). Để sử dụng priority queue một cách hiệu quả, các bạn nên học cách viết hàm so sánh để sử dụng cho linh hoạt cho từng bài toán.
**Khai báo**:
- Dạng 1 (sử dụng phép toán mặc định là less): ```priority_queue<kiểu_dữ_liệu> pq;``` (ưu tiên đưa phần tử lớn nhất ra)

- Dạng 2 (sử dụng phép toán khác): ```priority_queue<kiểu_dữ _liệu, vector<kiểu_dữ _liệu>, greater<kiểu_dữ _liệu>> q; //phép toán greater```
(ưu tiên đưa phần tử bé nhất ra)

Phép toán khác cũng có thể do người dùng tự định nghĩa. Ví dụ cách khai báo ở dạng 2 tương đương với:

struct cmp{
 bool operator() (int a,int b) {return a>b;}
};
main() {
 …
 priority_queue <int, vector<int>, cmp > q;
} 

**Các hàm hay sử dụng với priority queue:**
- size: trả về kích thước hiện tại của priority queue. Độ phức tạp: $O(1)$. Cú pháp: $pq.size()$.
- empty: true nếu priority queue rỗng, và ngược lại. Độ phức tạp: $O(1)$. Cú pháp: $pq.empty()$.
- push: đẩy vào priority queue. Độ phức tạp: $O(logN)$. Cú pháp: $pq.push(x)$ (đẩy x vào priority queue).
- pop: loại bỏ phần tử ở đỉnh priority queue. Độ phức tạp: $O(logN)$. Cú pháp: $pq.pop()$.
- top : trả về phần tử ở đỉnh priority queue. Độ phức tạp: $O(1)$. Cú pháp: $pq.top()$.

# 4. Stack
Stack được thiết kế để hoạt động theo kiểu LIFO (Last - in first - out) (vào sau ra trước), tức là một kiểu danh sách mà việc bổ sung và loại bỏ một phần tử được thực hiển ở cuối danh sách. Vị trí cuối cùng của stack gọi là đỉnh (top) của ngăn xếp.
**Khai báo:** ```stack<kiểu_dữ_liệu> tên_stack;```
Ví dụ: $stack<int> st$;
**Các hàm hay sử dụng với stack:**
- size: trả về kích thước hiện tại của stack. Độ phức tạp: $O(1)$. Cú pháp: $st.size()$.
- empty: true nếu stack rỗng, và ngược lại. Độ phức tạp: $O(1)$. Cú pháp: $st.empty()$.
- push: đẩy vào stack. Độ phức tạp: $O(1)$. Cú pháp: $st.push(x)$ (đẩy x vào stack).
- pop: loại bỏ phần tử ở đỉnh stack. Độ phức tạp: $O(1)$. Cú pháp: $st.pop()$.
- top : trả về phần tử ở đỉnh stack. Độ phức tạp: $O(1)$. Cú pháp: $st.top()$.

# 5. Queue
Queue được thiết kế để hoạt động theo kiểu FIFO (First- in first - out) (vào trước ra trước), tức là một kiểu danh sách mà việc bổ sung được thực hiển ở cuối danh sách và loại bỏ ở đầu danh sách. Trong queue, có hai vị trí quan trọng là vị trí đầu danh sách (front), nơi phần tử được lấy ra, và vị trí cuối danh sách (back), nơi phần tử cuối cùng được thêm vào.
**Khai báo:** ```queue<kiểu_dữ_liệu> tên_queue;```
Ví dụ: $queue<int> q;$
**Các hàm hay sử dụng với queue:**
- size: trả về kích thước hiện tại của queue. Độ phức tạp: $O(1)$. Cú pháp: $q.size()$.
- empty: true nếu queue rỗng, và ngược lại. Độ phức tạp: $O(1)$. Cú pháp: $q.empty()$.
- push: đẩy vào cuối queue. Độ phức tạp: $O(1)$. Cú pháp: $q.push(x)$ (đẩy x vào cuối queue).
- pop: loại bỏ phần tử ở đầu queue. Độ phức tạp: $O(1)$. Cú pháp: $q.pop()$.
- front: trả về phần tử ở đầu queue. Độ phức tạp: $O(1)$. Cú pháp: $q.front()$.
- back: trả về phần tử ở cuối queue. Độ phức tạp $O(1)$. Cú pháp: $q.back()$.
# 6. Luyện tập
Đây là một số bài tập luyện tập trong sách [Competitive Programming Advanced](https://codedream.edu.vn/bo-sach-lap-trinh/) của Code Dream, đăng ký mua ngay để được luyện tập nhiều dạng bài về thuật toán khác, chấm bài online tại http://oj.codedream.edu.vn

**ÁP DỤNG GIẢI BÀI TOÁN TRUEBRAC:**
**Phân tích bài toán:**
*Nhận xét*: Do dãy ngoặc đúng có số dấu ngoặc mở và ngoặc đóng bằng nhau; giữa một cặp dấu ngoặc tương ứng là một dãy ngoặc đúng nên ta có thể làm như sau:
- Duyệt xâu cần kiểm tra.
- Khi gặp dấu ngoặc mở thì đẩy vào stack; còn khi gặp dấu ngoặc đóng thì kiểm tra nếu đỉnh stack có dấu ngoặc mở tương ứng với nó thì đẩy dấu ngoặc mở đó ra khỏi stack, ngược lại xâu không phải dãy ngoặc đúng.
- Sau khi duyệt hết xâu nếu stack rỗng thì xâu là dãy ngoặc đúng và ngược lại.

**Code mẫu:**

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define int int64_t
#define pii pair<int, int>
const int mx = 1e6 + 5;
const int mod = 1e9 + 7;
void sub() {
    string s;
    cin >> s;
    stack<int> st;
    for (int i = 0; i < s.size(); i++) {
        if (s[i]=='(' || s[i]=='[' || s[i]=='{' ) st.push(s[i]);
        else {
        	if (!st.empty() && ((s[i]==')' && st.top()=='(') || (s[i]==']' && st.top()=='[') || (s[i]=='}' && st.top()=='{'))) st.pop();
        	else {
        		cout << "NO";
        		return;
        	}
        }
    }
	if (st.empty()) cout << "YES";
	else cout << "NO";
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    sub();
    return 0;
}
//honguwu