# 前言

這個系列是我重新整理自己的演算法學習筆記，主軸沿用我當初寫的《APCS 考前準備》講義的脈絡，並補上 AP325（吳邦一教授）與 2023 CISCON 社群月演算法專題課程裡比較完整的觀念說明與複雜度分析。

這一章先介紹會反覆用到的資料結構與 STL 函式。這些東西本身不是「演算法」，但它們是後面所有章節的工具箱 —— 你選對容器，一題就從 O(n^2) 掉到 O(n log n) ；選錯容器，就算想法完全正確也會 TLE。

所以這章的重點不是背 API，而是理解每個容器的操作各要花多少時間。

# 關於程式碼來源

本系列的每段程式碼除了我自己寫的都會在第一行標註來源：

標註	意義
`// [來源：AP325]`	出自吳邦一教授的 AP325 教材
`// [來源：CISCON 2023]`	出自 2023 CISCON 社群月演算法專題課程
`// [來源：本文補充，待替換]`	為了補齊觀念而快速用 AI 補寫的範例，之後會替換成自己的寫法

參考資料：

AP325－從 APCS 實作題檢測三級到五級。吳邦一，2020/8/7
2023 CISCON 社群月演算法專題課程（動態規劃：陳俊安 Colten／貪心：Koying／枚舉：Fishhh／搜尋：高睿）
YUI HUANG 演算法學習筆記（https://yuihuang.com/apcs/）
C++ Reference（https://www.cplusplus.com/reference/）

# 先講複雜度：為什麼要在意

在挑資料結構之前，得先有個判斷標準。

時間複雜度是用來描述「當輸入量 n 變大時，程式執行時間成長的趨勢」，我們只保留成長最快的那一項，並且忽略常數。例如 3n^2 + 100n + 5 就寫成 O(n^2) ，因為 n 夠大的時候， n^2 這一項會完全主導。

# 由測資大小反推所需複雜度

這是解題時最實用的一招。一般線上測試系統的時限大約 1 秒，而現代電腦大約每秒可以做 10^8 到 10^9 次基本運算。所以看到題目的 n，就大致能反推該用什麼等級的演算法：

n 的大小	可接受的複雜度	常見對應解法
n ≤ 10	`O(n!)` 、 `O(2^n × n)`	全排列窮舉、回溯法
n ≤ 20~25	`O(2^n)`	子集合窮舉、折半枚舉
n ≤ 500	`O(n^3)`	三層迴圈、Floyd-Warshall
n ≤ 5000	`O(n^2)`	二維 DP、雙層迴圈
n ≤ 10^5 ~ 10^6	`O(n log n)`	排序、二分搜、掃描線、priority_queue
n ≤ 10^7 以上	`O(n)` 、 `O(log n)`	前綴和、單調隊列、數學推導

反過來用更有價值：題目給 n ≤ 2×10^5，就代表出題者不打算讓 O(n^2) 過，你要嘛排序、要嘛用 log 級的資料結構，這個資訊在你還沒想出解法時就已經幫你篩掉一半的方向了。

# 兩個一定要注意的地雷

整數 overflow。 C++ 的 int 大約只到 2.1 × 10^9 （2^31 - 1）。題目只要出現「答案可能超過 int 上限」、「總和不超過 10^18」這類敘述，就要用 long long 。更陰險的是中間過程 overflow：即使最終答案在範圍內，計算途中的乘積可能已經爆掉了。

	int a = 100000, b = 100000;
	long long c = a * b; // 錯！a*b 先以 int 運算就溢位了，之後才轉型
	long long d = (long long)a * b; // 對：先轉型再相乘

判斷式的 short-circuit evaluation。 C++ 的 && 和 || 是「短路求值」： A && B 只要 A 是 false 就不會去看 B。這個特性拿來防越界非常好用：

	// 正確：先確定 i 沒越界，才去讀 a [i]
	if (i < n && a[i] == target) { ... }

	// 錯誤：順序反過來，i == n 時會讀到陣列外
	if (a[i] == target && i < n) { ... }

# queue（佇列）

特性是 First In First Out（先進先出），像排隊一樣，先來的先服務。BFS 就是靠它實現的。

	queue<int> q; // 宣告
	q.push(x); // 把 x 放入 queue 中
	q.front(); // 讀取第一個元素（不會刪除）
	q.pop(); // 移除第一個元素（不會回傳值）
	q.empty(); // 判斷 queue 是否為空，為空 return true
	q.size(); // 回傳 queue 的大小
	q.swap(q2); // 跟另一個 queue 做交換

所有操作都是 O(1) 。

要特別注意 front() 和 pop() 是分開的兩個動作： front() 只是看， pop() 只是丟， pop() 本身不回傳值。所以取值的標準寫法是：

	auto e = q.front();
	q.pop();

# deque（雙向佇列）

跟 queue 的特性一樣，差別是多了許多方便的指令 —— 兩端都可以進出，而且支援隨機存取跟 iterator。

	deque<int> dq; // 宣告
	deque<int>::iterator it = dq.begin(); // 用 iterator 取值，it 是第一個元素
	auto it = dq.begin(); // 與上一行相同意思
	dq.assign(iterator, iterator+5); // 把 dq 裡的值替換成 iterator 到 iterator+5 的內容（左閉右開）
	dq.push_back(x); // 從最後面放入元素 x
	dq.push_front(x); // 從最前面放入元素 x
	dq.pop_back(); // 刪除最後一個元素
	dq.pop_front(); // 刪除第一個元素
	dq.insert(it, x); // 在 it 這個位址插入 x，原本的值往後推
	dq.erase(it); // 刪除在 it 這個位址的元素
	dq.erase(dq.begin(), dq.begin()+5); // 放入也可以是一個區間（左閉右開）
	dq.clear(); // 清空這個 deque
	dq.swap(dq2); // 跟另一個 deque 做交換

兩端的 push/pop 都是 O(1) ，中間的 insert/erase 是 O(n) 。

deque 最重要的應用是單調隊列（monotonic queue），可以在 O(n) 內求出所有「固定長度區間的最大／最小值」。後面動態規劃章節的「周伯通的基地台」就是靠它把 O(nk) 優化成 O(n) 。

下面這支程式建議實際跑一遍，觀察每一行做出的改變：

	int main(){
	deque<int> dq;
	int n=5;
	for(int i=0;i<n;i++) dq.push_back(i);
	deque<int> sec(8,80);
	auto it=sec.begin();
	*(it+3)=70;
	while(it!=sec.end())
	cout<<*it++<<" ";
	cout<<"\n";
	it=dq.begin();
	sec.assign(it,it+5);
	it=sec.begin();
	while(it!=sec.end())
	cout<<*it++<<" "; cout<<"\n";
	sec.insert(it+3,11);
	sec.erase(sec.begin(),sec.begin()+3);
	it=sec.begin();
	while(it!=sec.end())
	cout<<*it++<<" ";
	}

# stack（堆疊）

特性是先進後出（Last In First Out）。

	stack<int> stk; // 宣告
	stk.push(x); // 把 x 放入 stk
	stk.top(); // 取最上面的值
	stk.pop(); // 把最上面的值刪除
	stk.size(); //stk 的大小
	stk.empty(); //stk 是否為空，為空 return true
	stk.swap(stk2); // 把 stk 跟另一個 stack 裡面的東西交換

所有操作都是 O(1) 。

stack 的典型用途是括號配對、運算式求值，還有把遞迴改寫成迭代 —— 事實上遞迴本身就是靠系統的呼叫堆疊（call stack）運作的。後面「先加後乘與函數」那題就用到了 stack 來處理運算優先序。

# vector（動態陣列）

特性跟陣列一樣，不過在動態的使用上比陣列更有彈性。

	vector<int> v; // 宣告
	vector<vector<int>> vv; // 宣告二維的 vector
	vector<int> v(3); // 宣告長度為 3 的 vector，因為是 vector 所以可以繼續擴增
	vector<int> v(5, 8); // 宣告長度為 5、初始值都是 8 的 vector
	vector<int> v2 = v; // 把 v 的內容給我新宣告的 v2
	v.front(); // 讀取 v 中第一個元素
	v.back(); // 讀取 v 中最後一個元素
	v.push_back(x); // 把元素 x 由後加進 v 中
	v.insert(v.begin()+i, x); // 在索引值 i 的地方插入 x，其他值往後推
	v.pop_back(); // 刪除最後一個元素
	v.erase(v.begin()+i); // 刪除第 i 個元素（idx 從 0 開始）
	v.erase(v.begin()+i, v.begin()+j); // 刪除 (i,j) 區間的值（左閉右開）
	v.clear(); // 清空 v
	v.size(); // 回傳 v 的長度
	v.empty(); // 回傳 v 的長度是否為 0，為 0 則 return true

複雜度： push_back 與 pop_back 是均攤 O(1) ，用 [] 隨機存取是 O(1) ，中間的 insert ／ erase 是 O(n) 。

這裡的「均攤 O(1) 」值得解釋一下：vector 的容量滿了的時候會重新配置一塊兩倍大的記憶體並搬移所有元素，那一次是 O(n) 。但因為容量是倍增的，這種昂貴操作發生的頻率越來越低，平均分攤到每次 push_back 上仍然是常數時間。

	int main(){
	vector<vector<int>> vv;
	vector<int> v(5,8);
	vv.push_back(v);
	vv.push_back(v);
	auto it=vv[0].begin()+3;
	*it=5;
	vv.front().front()=6;
	for(auto i:vv){
	for(auto j:i){
	cout<<j<<" ";
	}
	cout<<"\n";
	}
	}

補充一個實用寫法，宣告二維 vector 並指定大小與初始值：

vector<vector<int>> vv(n, vector<int>(m, 0));  //n 列 m 行，全部初始化為 0

# set（集合）

特性是由小到大排序且去除重複元素，實作是一棵平衡二元樹（紅黑樹）。因為是一棵平衡的二元樹，所以對一個 set 做增加、刪除或查找的時間複雜度是 O(log n) 。

	set<int> st; // 宣告。如果是 pair<int,int> 會先根據 first 排序再來 second
	st.insert(x); // 把 x 加入 set
	st.erase(x); // 把 x 從 set 中刪除
	st.clear(); // 清空 set
	auto it = st.begin(); // 用 iterator 儲存 set 中的第一個值（最小）
	x = *st.rbegin(); // 把 set 中的最後一個值（最大）給 x
	st.size(); // 回傳 set 的大小
	st.empty(); // 回傳 set 是否為空
	st.count(x); // 尋找 set 是否存在 x，回傳 true or false
	auto it = st.find(x); // 在 set 中尋找 x，找到回傳指向它的 iterator，沒找到回傳 st.end ()
	auto it = st.lower_bound(x); // 回傳一個 iterator 指向第一個大於等於 x 的元素
	x = *st.upper_bound(x); // 回傳第一個大於 x 的元素

這裡有個容易踩的坑：set 有自己的 lower_bound 成員函式，一定要用它，不要用 <algorithm> 裡的全域 lower_bound 。全域版本假設資料是隨機存取的，套在紅黑樹上會退化成 O(n) ；成員版本才是走樹的 O(log n) 。

	auto it = st.lower_bound(x); // 對：O (log n)
	auto it = lower_bound(st.begin(), st.end(), x); // 錯：O (n)

# multiset

特性跟 set 一樣，只是會保留重複的元素。用法跟 set 差不多，下面介紹不同的部分：

	mst.erase(value); // 刪除所有值為 value 的元素
	mst.erase(mst.find(value)); // 只刪除第一個值為 value 的元素
	mst.count(value); //return 符合 value 的數量

注意 erase(value) 跟 erase(find(value)) 的差別非常大，這是實務上很常寫錯的地方 —— 前者會把所有相同的值一次清光。如果你只是想拿掉一個，一定要用 find 。

count(value) 的複雜度是 O(log n + k) ，k 是符合的元素個數。

multiset 在貪心演算法裡特別有用，因為它同時支援「動態插入刪除」跟「查詢最接近某值的元素」，後面「機器出租」那題就是典型應用。

# map（映射）

跟 set 一樣是用紅黑樹實現，特性是提供了鍵值對（key-value pair）的映射關係，常用在離散化上。

	map<string, pair<int,int>> mp; // 宣告
	map<int,int> mp; // 宣告
	mp[key] = value; //map 給值的方式，key 對應到的 value
	mp.count(key); // 回傳是否找到 key，return true or false
	mp.erase(key); // 移除 key
	mp.clear(); // 清空 map
	value = mp[key]; // 把 mp [key] 對應到的值給 value
	mp.size(); // 回傳 mp 的大小
	mp.empty(); // 回傳 mp 是否為 0
	mp.swap(mp2); //mp 跟 mp2 交換

增刪查都是 O(log n) ，而且走訪時會按照 key 由小到大的順序。

有一個很常見的陷阱： mp[key] 如果 key 不存在，會直接建立一個預設值 0 的項目。所以純粹想「檢查存在性」時要用 count() 或 find() ，不要用 mp[key] ，否則你的 map 會在檢查過程中默默長大：

	if (mp[key] != 0) { ... } // 錯：即使 key 不存在也會被建立出來
	if (mp.count(key)) { ... } // 對

begin() 跟 end() 還有如何遍歷整個 map 在以下的程式進行說明：

	int main(){
	map<char,pair<int,int>> mp;
	mp['B']={8,7};mp['A']={2,2};mp['C']={4,1};
	for(auto pii:mp)
	cout<<pii.first<<" "<<pii.second.first<<" "<<pii.second.second<<"\n";
	cout<<"-=-=-=-\n";
	for(auto it=mp.begin();it!=mp.end();it++)
	cout<<it->first<<" "<<it->second.first<<" "<<it->second.second<<"\n";
	cout<<"-=-=-=-\n";
	for(auto it=mp.rbegin();it!=mp.rend();it++)
	cout<<(it).first<<" "<<(it).second.first<<" "<<(*it).second.second<<"\n";
	}

# 離散化

離散化是 map 最重要的應用，值得單獨講。

有些題目的數值範圍很大（例如座標到 10^9 ），但實際出現的數字很少（例如只有 10^5 個）。這時候你不可能開一個 10^9 大的陣列，但可以把這些數字「重新編號」成 0, 1, 2, ...，壓縮到能開陣列的範圍：

	// 方法一：用 map 直接映射
	map<int,int> id;
	int cnt = 0;
	for (int x : a) if (!id.count(x)) id[x] = cnt++;

	// 方法二：排序去重後二分搜（比較快，常數小）
	vector<int> tmp = a;
	sort(tmp.begin(), tmp.end());
	tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
	// 之後 x 的新編號就是：
	int newId = lower_bound(tmp.begin(), tmp.end(), x) - tmp.begin();

方法二的 unique 會把相鄰的重複元素移到後面並回傳新的結尾位置，所以要先排序再用，而且要搭配 erase 才真的縮短容器。

# unordered_map

提供了一個將鍵映射到值的集合。與 map 不同，unordered_map 不會將其元素儲存在排序順序中，而是通過使用哈希表實現元素的儲存和查找（時間複雜度 O(1) ）。用法跟 map 幾乎一樣，需要注意的是 unordered_map 沒有 rbegin() 跟 rend() 。

要提醒的是，那個 O(1) 是平均複雜度，最壞情況（大量雜湊碰撞）會退化成 O(n) 。在競賽場合偶爾會遇到針對雜湊函數設計的惡意測資，如果 unordered_map 莫名其妙 TLE，換回 map 試試看。另外，鍵的順序不固定，需要照順序輸出時只能用 map。

# priority_queue（優先佇列）

特性是資料預設由大到小，可以快速取得最大值。跟 multiset 有些許地方相似可是不一樣 —— 在取最大值或最小值時 priority_queue 可以用 O(1) 的速度，這裡就是最主要的差別。

	priority_queue<int> pq; // 宣告
	pq.push(x); // 把 x 加入 priority_queue
	x = pq.top(); // 取出 pq 中優先度最大的元素
	pq.pop(); // 移除 pq 中優先度最大的元素
	pq.empty(); //pq 是否為空
	pq.size(); //pq 的大小

複雜度： top() 是 O(1) ， push() 跟 pop() 是 O(log n) 。

它的底層是二元堆積（binary heap），用一個陣列模擬完全二元樹，父節點永遠不小於子節點。所以取最大值就是看陣列第 0 格， O(1) ；而插入或刪除後需要沿著樹「上浮」或「下沉」來恢復性質，樹高是 log n ，所以是 O(log n) 。

跟 multiset 比較：multiset 能取最大也能取最小、還能查找任意值，但常數比較大；priority_queue 只能取一端，但快很多。只需要一端就用 priority_queue，需要兩端或查找就用 multiset。

如果想改變 priority_queue 的排序方式，例如想從由大到小變成由小到大，可以參考下面的方式：

	#include <bits/stdc++.h>
	using namespace std;
	struct cmp{
	bool operator()(const int &lhs, const int &rhs){
	return (lhs > rhs);
	}
	};
	class mycomparison{
	bool reverse;
	public:
	mycomparison(const bool &revparam = false){
	reverse = revparam;
	}
	bool operator()(const int &lhs, const int &rhs){
	if (reverse)
	return (lhs > rhs);
	else
	return (lhs < rhs);
	}
	};
	int main(){
	priority_queue<int, vector<int>, cmp> pq1;
	priority_queue<int, vector<int>, mycomparison> pq2(true);
	for(int i=0;i<10;i++) pq1.push(i);
	for(int i=0;i<10;i++) pq2.push(i);
	while(!pq1.empty()){cout<<pq1.top()<<" ";pq1.pop();}
	cout<<"\n";
	while(!pq2.empty()){cout<<pq2.top()<<" ";pq2.pop();}
	}

不過一般在使用時有個偷吃步的方法，就是改變正負號，這樣排序就會顛倒了，讀出值的時候要記得變回去就好。

	priority_queue<int> pq;
	pq.push(-x); // 存進去的時候取負
	int val = -pq.top(); // 拿出來的時候變回正，這樣拿到的就是最小值

另外還有一個標準寫法，用 greater 直接做出小根堆，比自訂 struct 簡潔：

priority_queue<int, vector<int>, greater<int>> pq;  // 由小到大，top () 是最小值

# 常用的 STL 函式

	sort(a, a+n, cmp); // 範圍是左閉右開，預設是由小到大
	sort(v.begin(), v.end(), cmp); // 排序，cmp 是自訂排序函數
	memset(a, 0, sizeof(a)); // 將 a 陣列所有的值都設成 0
	swap(A, B); // 交換 A 跟 B，記得 A 跟 B 資料型態要一樣
	reverse(a, a+n); // 將指定範圍內的元素順序倒轉，範圍也是左閉右開
	reverse(v.begin(), v.begin()+i); // 我印象中的全部 STL 函數都是左閉右開
	auto it = lower_bound(v.begin(), v.end(), val); // 找到第一個大於等於 val 的位置
	int x = *upper_bound(v.begin(), v.end(), val); // 找到第一個大於 val 的值
	int idx = upper_bound(v.begin(), v.end(), val) - v.begin(); // 找到第一個大於 val 的 idx

幾點補充：

sort 是 O(n log n) ，實作上是 introsort（快排 + 堆排 + 插入排序的混合），不保證穩定。需要穩定排序（相同鍵值維持原順序）要用 stable_sort 。
memset 是逐位元組填值，所以只有填 0 和 -1 是安全的。填其他值會出事，例如 memset(a, 1, sizeof(a)) 得到的不是 1 而是 0x01010101 。要填其他初始值請用 fill 。
lower_bound 跟 upper_bound 都是 O(log n) ，但前提是資料必須已經由小到大排序好。

# cmp 函式的寫法

自訂排序函數有一個非常重要的規則：cmp 必須是嚴格弱序（strict weak ordering），也就是相等的時候一定要回傳 false 。

	bool cmp(int x, int y){
	return x > y; // 對：由大到小，相等時回傳 false
	}
	bool cmp_bad(int x, int y){
	return x >= y; // 錯！相等時回傳 true，會導致 sort 執行期崩潰
	}

這個錯誤很陰險，小測資看起來正常，資料量一大就 runtime error。

pair 的排序預設是由 first 由小到大，如果 first 一樣就根據 second 由小到大，從下面的範例程式就可以得知：

	bool cmp2(pair<int,int> x, pair<int,int> y){
	if(x.first!=y.first) return x.first>y.first;
	else return x.second>y.second;
	}

# 自己寫二分搜

binary_search 是我自己寫的二分搜，因為 lower_bound 跟 upper_bound 都必須符合資料由小到大才可以查找。如果遇到一些比較特殊的情況要不方便使用 STL 函式，可以參考我寫的二分搜。這是我覺得最好的寫法，不管你要找第一個大於 val、第一個大於等於 val、第一個小於 val、第一個小於等於 val，都可透過修改 if 裡面的判斷式跟 return 的結果來快速更改成你需要的程式。

	int binary_search(int l,int r,int val,int arr[]){ // 區間為左開右開
	int mid=(l+r)>>1; // 注意這個二分搜是寫給由大到小的數組用的
	while((l+1)!=r){
	if(arr[mid]>val){
	l=mid;
	}else{
	r=mid;
	}
	mid=(l+r)>>1;
	}
	return l;
	}

這種「左開右開」寫法的核心是維持一個不變量（invariant）： l 永遠指向滿足條件的位置， r 永遠指向不滿足的位置。迴圈條件 (l+1)!=r 表示兩者相鄰時就停止，此時 l 就是最後一個滿足條件的位置。

用這種寫法的好處是不會有 off-by-one 的困擾 —— 因為初始呼叫時 l 和 r 都放在陣列外（例如 binary_search(-1, n, val, a) ），邊界情況自然被涵蓋，不用另外特判。

>>1 就是除以二的意思，位元運算會比 / （除號）還要快。

下面是一支完整的範例程式，協助了解上述函式的用法。在讀的時候建議把程式複製到編譯器執行後觀察每一行做出的改變：

	#include <bits/stdc++.h>
	using namespace std;
	bool cmp(int x,int y){
	return x>y;
	}
	bool cmp2(pair<int,int> x,pair<int,int> y){
	if(x.first!=y.first) return x.first>y.first;
	else return x.second>y.second;
	}
	int binary_search(int l,int r,int val,int arr[]){
	int mid=(l+r)>>1;
	while((l+1)!=r){
	if(arr[mid]>val){
	l=mid;
	}else{
	r=mid;
	}
	mid=(l+r)>>1;
	}
	return l;
	}
	int n=10,a[100];
	vector<int> b;
	vector<pair<int,int>> c;
	int main(){
	for(int i=0,temp;i<n;i++){
	temp=rand()%n+1;
	a[i]=temp;
	b.push_back(temp);
	c.push_back({temp,rand()%n+1});
	}
	cout<<"\na = ";
	for(int i=0;i<n;i++) cout<<a[i]<<" ";
	cout<<"\nb = ";
	for(auto i:b) cout<<i<<" ";
	cout<<"\na = ";
	sort(a,a+n,cmp);
	sort(b.begin(),b.end());
	for(int i=0;i<n;i++) cout<<a[i]<<" ";
	cout<<"\nb = ";
	for(auto i:b) cout<<i<<" ";
	cout<<"\nc = ";
	sort(c.begin(),c.end());
	for(auto i:c) cout<<i.first<<" "<<i.second<<",";
	cout<<"\nc = ";
	sort(c.begin(),c.end(),cmp2);
	for(auto i:c) cout<<i.first<<" "<<i.second<<",";
	cout<<"\n";
	int val=6;
	auto it=lower_bound(b.begin(),b.end(),val);
	int idx=lower_bound(b.begin(),b.end(),val)-b.begin();
	cout<<*it<<" "<<idx<<"\n";
	it=upper_bound(b.begin(),b.end(),val);
	idx=upper_bound(b.begin(),b.end(),val)-b.begin();
	cout<<*it<<" "<<idx<<"\n";
	idx=binary_search(-1,n,val,a);
	cout<<a[idx]<<" "<<idx;
	}

範例輸出：

a = 2 5 10 9 3 6 2 2 6 8   // 原始
b = 2 5 10 9 3 6 2 2 6 8   // 原始
a = 10 9 8 6 6 5 3 2 2 2   // 由大到小排序
b = 2 2 2 3 5 6 6 8 9 10   // 由小到大排序
c = 2 2, 2 8, 2 8, 3 5, 5 1, 6 3, 6 6, 8 7, 9 9, 10 5,   // pair 的原始
c = 10 5, 9 9, 8 7, 6 6, 6 3, 5 1, 3 5, 2 8, 2 8, 2 2,   // pair 排序過後
6 5    // b 數組第一個大於等於 6 的數跟那個數的索引值
8 7    // b 數組第一個大於 6 的數跟那個數的索引值
8 2    // a 數組第一個大於 6 的數跟那個數的索引值（注意 a 陣列是由大到小）
// 如果函式裡的 return l 改成 return r 就會回傳遞一個小於等於 val 的 idx

# I/O 加速

最後提一件在考試時很實際的事。C++ 的 cin ／ cout 預設會跟 C 的 scanf ／ printf 同步，這個同步機制讓它們變得很慢。輸入量大的時候（例如 10^5 筆以上）光是讀入就可能 TLE。

解法是在 main() 開頭加上這兩行：

	ios::sync_with_stdio(0);
	cin.tie(0);

sync_with_stdio(0) 解除與 C 標準 I/O 的同步， cin.tie(0) 解除 cin 與 cout 的綁定（預設每次 cin 前都會先 flush cout ）。

加了之後就不要再混用 scanf ／ printf ，否則輸出順序會亂掉。另外，用 "\n" 取代 endl 也能加速，因為 endl 每次都會強制 flush 緩衝區。

這兩行在我原本的講義裡幾乎都沒打，只是因為不想占版面 —— 但實際檢定或比賽的時候記得要打。

# 小結

這章的重點整理成一張表，之後解題選容器時可以回來查：

容器	插入	刪除	查找	取極值	有序	典型用途
vector	`O(1)` 均攤（尾端）	`O(1)` （尾端）	`O(n)`	—	否	通用陣列、鄰接串列
deque	`O(1)` （兩端）	`O(1)` （兩端）	`O(n)`	—	否	單調隊列、滑動視窗
stack	`O(1)`	`O(1)`	—	—	否	括號配對、運算式
queue	`O(1)`	`O(1)`	—	—	否	BFS
set / map	`O(log n)`	`O(log n)`	`O(log n)`	`O(log n)` 兩端	是	去重、離散化、查找鄰近值
multiset	`O(log n)`	`O(log n)`	`O(log n)`	`O(log n)` 兩端	是	允許重複的動態查找
unordered_map	`O(1)` 平均	`O(1)` 平均	`O(1)` 平均	—	否	純查找、計數
priority_queue	`O(log n)`	`O(log n)`	—	`O(1)` 單端	部分	貪心、Dijkstra

下一章開始進入真正的演算法，從遞迴講起 —— 它是後面分治、DP、圖論走訪的共同基礎。

# 練習題

（之後補上）