奇技淫巧。

inline 傳奇

2025/2/11 upd.

我們自古以來都一直堅信，當代 C++ 中給函數前面加 inline 幾乎沒有優化效果。

但是今天，這一條被顛覆了。在一道題中，某長安19路的代碼在給線段樹相關函數加上 inline 后，從 TLE 卡成 AC，并且優化效果達 300ms 以上。

究竟是他常數過大，抑或是評測機道德淪喪，我們不得而知。

2025/2/14 upd.

后來，筆者在一些有名的數據結構題中將不加 inline 和加了 inline 的代碼的時間作以比對發現，大多數 OJ 加上 inline 的確有優化效果但不多，大抵是平均每個測試點 5ms 左右。但是，沒有出現負優化。

所以我們可以得出一個初步結論：inline 的優化效果取決于評測機速度。

---

導論

任何奇技淫巧以能在比賽時使用為標準。

任何顛覆了傳統且對比賽有幫助的東西統稱奇技淫巧。奇技淫巧抑或是能減少碼量，抑或是能優化時空，抑或是能亂搞，抑或只是為了裝逼。目前主要分為如下幾個類別：

• 語法類：新標準中的語法，目前支持到 C++14。也會包含一些冷門語法。
• STL 類：包括但不限于 STL、exSTL（如 pb_ds、rope 等）。其實 STL 也算語法。
• 隨機化類：隨機化函數、隨機化算法。
• 卡常類：顧名思義。
• 位運算類：顧名思義。其實位運算也算卡常。

更廣義的奇技淫巧包括但不限于：

• 搜索相關。包括但不限于最優化、剪枝。
• 壓行相關。這一點用教練的話說，人各有志。
• ……

這些限于篇幅，且不完全符合對奇技淫巧的定義，不做講解。

語法類

參考這篇專欄以及網上各路博客。

請注意，任何自帶的函數常數都不如手寫的，特殊標明除外。

C++98

庫函數

• find(bg, ed, val)：返回第一個等于 \(\mathit{val}\) 的元素指針。復雜度 \(O(N)\)。
• fill(bg, ed, val)：將 \([\mathit{bg},\mathit{ed})\) 的所有元素賦值為 \(\mathit{val}\)。復雜度 \(O(N)\)。

  當只需對 \(n\) 范圍的數組初始化而非對整個數組初始化時，筆者常用于替代常數較大的 memset。其余部分與 memset 相差不大。

• copy(bg1, ed1, bg2)：將 \([\mathit{bg}_1,\mathit{ed}_1)\) 的元素復制到 \(\mathit{bg}_2\)。復雜度 \(O(N)\)。

  與 memcpy 作用疑似差別不大。

• nth_element(bg, md, ed, cmp = less<>())：將 \([\mathit{bg},\mathit{ed})\) 重新排序，將小于等于 \(\mathit{md}\) 的元素排在其之前，大于等于的元素排在其之后。復雜度 \(O(N)\)。第四個參數為比較函數。
• max_element/min_element(bg, ed, cmp = less<>())：返回指向 \([\mathit{bg},\mathit{ed})\) 中最大/最小元素的指針。復雜度 \(O(N)\)。第三個參數為比較函數。

  求數組最大值就可以直接寫：mx = *max_element(a + 1, a + n + 1)。

• next_permutation/prev_permutation(bg, ed, cmp = less<>())：下一個/上一個排列。第三個參數為比較函數。
• count(bg, ed, val)：返回 \([\mathit{bg},\mathit{ed})\) 中元素 \(\mathit{val}\) 的個數，復雜度 \(O(N)\)。
• replace(bg, ed, val1, val2)：將 \([\mathit{bg},\mathit{ed})\) 中所有等于 \(\mathit{val}_1\) 的元素替換為 \(\mathit{val}_2\)，復雜度 \(O(N)\)。

GNU 私貨

不在 C++ 標準中，是 GNU 的私貨，比賽時可以使用。

• __lg(x)：返回 \(\lfloor\log_2 x\rfloor\)。復雜度 \(O(1)\)。

  與 C++11 中的 log2(x) 函數作用相同。

• __gcd(x, y)：返回 \(\gcd(x,y)\)。復雜度是小常數的 \(O(\log N)\)。注意，返回值的符號不一定是正。

numeric 庫

有人說它很好用，個人覺得一般。

• accumulate(bg, ed, val)：求區間和與 \(\mathit{val}\) 相加的值，但注意返回值的類型和 \(\mathit{val}\) 的類型相同，使用時需注意溢出問題。復雜度 \(O(N)\)。
• partial_sum(bg1, ed1, bg2)：對 \([\mathit{bg}_1,\mathit{ed}_1)\) 做前綴和并存入 \(\mathit{bg}_2\)。復雜度 \(O(N)\)。

  用于原地求前綴和。但一般求前綴和都是邊讀邊求的，所以個人認為作用一般。

• adjacent_difference(bg1, ed1, bg2)：與 partial_sum 同理，用于原地差分。復雜度 \(O(N)\)。

functional 庫

常用的：less<>/greater<>。簡單排序再也不用寫 cmp 了。

實際上還有類似的：

• equal_to<>：返回 x == y。
• not_equal_to<>：返回 x != y。
• less_equal<>/greater_equal<>：返回 x <= y 和 x >= y。

剩下的個人感覺不常用了，可以自己打開頭文件看。

cmath 庫

• abs(x)/fabs(x)：返回整型/浮點型的 \(|x|\)。注意對應清楚類型，避免造成慘案。
• fmod(x, y)：可以用于浮點數的模運算。關鍵時刻有大用。
• exp(x)：返回 \(\mathrm e^x\)。
• log(x)：返回 \(\ln x\)。注意 \(\lg x\) 是 log10(x)，請不要對號入座。
• floor/ceil(x)：大家都會用，但注意返回值為浮點型。

此外，cmath 庫中定義了很多常量，使用方法：

1. 代碼開頭在引用頭文件前必須寫一句 #define _USE_MATH_DEFINES，不寫是用不了的，也可以寫頭文件里剩下的那幾個；
2. 然后就可以使用里面的各種常量了。下面直接放頭文件，注意有第二個下劃線的是除以的意思，如 M_PI_2 就是 \(\pi/2\)，M_1_PI 就是 \(1/\pi\)。比較常用的就是一個 \(\pi\) 和一個 \(\mathrm e\)。

#if !defined(__STRICT_ANSI__) || defined(_XOPEN_SOURCE) || defined(_GNU_SOURCE) || defined(_BSD_SOURCE) || defined(_USE_MATH_DEFINES)
#define M_E		2.7182818284590452354
#define M_LOG2E		1.4426950408889634074
#define M_LOG10E	0.43429448190325182765
#define M_LN2		0.69314718055994530942
#define M_LN10		2.30258509299404568402
#define M_PI		3.14159265358979323846
#define M_PI_2		1.57079632679489661923
#define M_PI_4		0.78539816339744830962
#define M_1_PI		0.31830988618379067154
#define M_2_PI		0.63661977236758134308
#define M_2_SQRTPI	1.12837916709551257390
#define M_SQRT2		1.41421356237309504880
#define M_SQRT1_2	0.70710678118654752440
#endif

__builtin 家族

全都是 GNU 私貨，復雜度 \(\boldsymbol{O(\log\log n)}\) 且常數很小，一定比手寫快。

如果 \(\boldsymbol x\) 的類型是 long long，請務必使用 __builtin_xxxll(x)。

• __builtin_popcount(x)：返回 \(x\) 在二進制下 \(1\) 的個數。
• __builtin_parity(x)：返回 \(x\) 在二進制下 \(1\) 的個數的奇偶性，快于 __builtin_popcount(x) & 1。
• __builtin_ffs(x)：返回二進制下最后一個 \(1\) 是從右往左第幾位。
• __builtin_ctz(x)：返回二進制下后導零的個數，\(x=0\) 時未定義。
• __builtin_clz(x)：返回二進制下前導零的個數，\(x=0\) 時未定義。

C++11

從 C++98 到 C++11 是一次重大的飛躍，許許多多非常實用的函數與語法如雨后春筍般出現。

新語法

nullptr

以后所有的 NULL 都寫成 nullptr。

因為 NULL 實際上被實現成了含糊不清的 #define NULL 0，nullptr 徹底做出了區分。

using 替代 typedef

// Before
typedef long long ll;
typedef pair<int, int> pii; // CE，模板不是類型

// Now
using pii = pair<int, int>; // 編譯成功，與 typedef 有一樣的效果

constexpr 關鍵字

與 const 的區別：const 意義為 “只讀”，constexpr 意義為 “常量”。

被 constexpr 修飾的變量/函數在編譯時就被計算，效率更高。所以請盡量使用 constexpr。剩余更高深的應用自行 BDFS。

auto 關鍵字

• 用于自動聲明變量類型，但注意必須初始化。
• 也可用于函數自動推導返回值類型。（C++14）
• 也可在 Lambda 的形參中出現，但不能在普通函數的形參中出現。（C++14）

Lambda 表達式

• 語法自行 BDFS，用于快速寫一些小函數，自帶 inline。
• 捕獲列表方面，全局 Lambda 自動為 &，局部 Lambda 不會捕獲。
• 捕獲外部變量盡量使用 &，避免無謂的變量拷貝耗費時間。

基于范圍的 for 循環

// Before
for (int i = 0; i < g[u].size(); ++i) ... // 好麻煩，常數大（不斷調用 size 函數）
for (vector<int>::iterator it = g[u].begin(); it != g[u].end(); ++it) ... // 常數小，但更麻煩

// Now
for (auto v : g[u]) // 舒服

• 極其常用于圖的遍歷等。
• 如果 for 循環內要修改，寫成 for(auto &v : g[u])。
• 遍歷范圍為整個數組。

emplace

許多 STL 的容器中出現的新函數：

• 對于 set 等容器，s.insert(x) 等于 s.emplace(x)；
• 對于 stack 和 queue 等容器，q.push(x) 等于 q.emplace(x)；
• 對于 vector 等容器，v.push_back(x) 等于 v.emplace_back(x)；
• 以此類推。

幾乎所有的 “插入、添加” 型成員函數都有 emplace 的版本。emplace 通過調用構造函數來插入，相較于原來的拷貝方式效率更優。所以它的用法也有不一樣：

vector<pair<int, int>> v; // 以前兩個>中間要加個空格，現在也不需要了
// Before
v.push_back(make_pair(a, b));
v.push_back({a, b});
// Now
v.emplace_back(a, b);

只要有構造函數，類似的寫法同樣可應用于結構體。

advance 函數

語法：advance(it, num)，其中 \(\mathit{it}\) 是一個迭代器，\(\mathit{num}\) 是一個整數。

作用是將迭代器 \(\mathit{it}\) 前進 \(\mathit{num}\) 位。

它有什么用，相信不需要我再多說。但要注意，對于序列式容器（vector、deque、list），復雜度 \(O(1)\)；對于關聯式容器（set、map），復雜度 \(O(n)\)。

distance 函數

語法：distance(it1, it2)，其中兩個參數都是迭代器。

作用是返回兩個迭代器之間的距離。復雜度同樣，對于序列式容器（vector、deque、list），復雜度 \(O(1)\)；對于關聯式容器（set、map），復雜度 \(O(n)\)。

如果兩個參數填反了，對于序列式容器，會返回負數；對于關聯式容器，UB。

shrink_to_fit

• 首先請 BDFS 一下 STL 容器的容量（capacity）和大小（size）的區別。
• 作用就是使其 capacity 調整為 size 的大小。在空間不緊張的情況下用途不大。
• 在空間緊張的情況下用途巨大。——2024/10/6 upd.

decltype 關鍵字

用于推導返回值類型并將其作為新變量的類型，如：

int a = 1953615, b = 198964;
decltype(a + b) c; // 此時 c 是 int 類型

除非你真的不知道應該給新變量什么類型，否則可能沒用。

庫函數

algorithm 庫

• shuffle(bg, ed, gen)：隨機打亂，其中 gen 是一個 mt19937。請不要再使用 random_shuffle。如果不知道什么是 mt19937 請參閱隨機化部分。
• is_sorted(bg, ed)：判斷 \([\mathit{bg},\mathit{ed})\) 是否升序排序，復雜度 \(O(N)\)。
• minmax(a, b)：返回一個 pair，其 first 為二者較小值，second 為二者較大值。
• minmax(l)：\(l\) 是一個列表，返回一個 pair，前者為列表最小值，后者為列表最大值。復雜度 \(O(|l|)\)。
• minmax_element(bg, ed)：返回一個 pair，前者為 \([\mathit{bg},\mathit{ed})\) 中最小值，后者為最大值。
• max/min(l)：其中 \(l\) 是一個用大括號括起來的列表，返回 \(l\) 中最大/最小的元素。復雜度 \(O(|l|)\)。

  再也不用 max 套 max 了。

numeric 庫

• iota(bg, ed, val)：將 \([\mathit{bg},\mathit{ed})\) 中的元素依次賦值為 \(\mathit{val},\mathit{val}+1,\mathit{val}+2,\cdots\)，復雜度 \(O(N)\)。

  用于原地初始化并查集。

iterator 庫

• prev/next(it)：返回迭代器 \(\mathit{it}\) 的前驅/后繼。

  再也不用擔心某些迭代器不能 +1-1 的問題了。

• begin/end(container)：其中 \(\text{container}\) 是一個 STL 容器，作用等于容器自帶的 begin() 和 end() 函數。除了短一個字符沒什么區別。

functional 庫

一句話作用：把一個函數當作一個變量存起來，可保存為單個變量或數組，可正常遍歷。

個人認為功能不強，語法請自行 BDFS。

random 庫

詳見隨機化部分。

cmath 庫

• exp2(x)：返回 \(2^x\)。

  如果 \(x\) 是整數，不如用 1 << x。

• log2(x)：返回 \(\log_2(x)\)。
• hypot(x, y)：返回 \(\sqrt{x^2+y^2}\)。

  歐氏距離從此一步得。

剩下的還有 STL 中的 tuple、構造函數等，它們要么是作用不大，要么是早已融入我們的代碼中，在此不提。

這里所說的 “構造函數” 指的是更高級的構造函數，普通的構造函數相信大家都會，更高級的咱也用不著。

C++14

字符串帶轉義字符

以前的字符串中出現轉義字符都需要反斜杠 \ 來修飾。

現在：char * str = R"(abc\db'\t")";。這樣聲明的字符串 \(\mathit{str}=\texttt{abc\\db'\\t"}\)。

語法就是 R"(...)"，括號內隨便寫什么都不會被轉義。

整型字面量分隔符

1. 在整型前面輸入 0b 代表是二進制，與八進制的 0、十六進制的 0x 類似。例：int a = 0b1101101001。
2. 在整型中插入 ' 作為分隔符，作用是方便閱讀而不影響編譯。例：

int wdz = 0b1'000'001'000;
int xx = 0x2'0'9; // 都是可以正常編譯的

比較雞肋是吧，因為有用的前面或多或少都提了。

STL 類

STL 是 C++ 獨有的最龐大的奇技淫巧。

STL

vector

設 \(v\) 是一個 vector。

• 便利的初始化：構造函數的第一個參數是長度，第二個參數是初始化的值。相信大家都會。但是如果 \(v_1\) 是一個 vector，還可以這么寫：vector<int> v2(v1)，表示把 \(v_1\) 中的元素拷貝到 \(v_2\)。也可以利用迭代器拷貝一部分。

• 調用 v.front() 和 v.back() 可以獲取到首尾元素的引用。更優雅。

• v.begin() 和 v.end() 是前閉后開的正序迭代器。v.rbegin() 和 v.rend() 是前開后閉的逆序迭代器。

• v.insert() 可以向 vector 中的某個位置插入元素。第一個參數永遠是一個迭代器。后面的參數可以是一個元素，可以是一個大括號列表，可以是別的容器的首尾指針/迭代器，甚至可以是一個數 \(n\) 加一個元素（表示插入 \(n\) 個這樣的元素），表示在迭代器前面的位置插入元素。注意復雜度是線性的。

• v.erase() 與 insert() 同理，可以刪除某個迭代器或區間的元素，復雜度也是線性的。

• swap() 函數支持交換兩個 vector，常數復雜度。

• v.assign() 可以將 vector 清空并重新賦值，線性復雜度，容量只增不減，之前的所有迭代器全部失效，分三種用法：

1. v.assign(count,value)，用 \(\mathit{count}\) 份 \(\mathit{value}\) 填充 \(v\)；
2. v.assign(first,last)，其中 \(\mathit{first}\) 和 \(\mathit{last}\) 都是指針或迭代器，意為用 \([\mathit{first},\mathit{last})\) 填充 \(v\)；
3. v.assign({})，意為用一個列表中的元素填充 \(v\)。

容量相關（2024/10/6 upd.）

vector 真正占空間的是容量，請務必在毒瘤題中注意 vector 的容量問題，及時釋放不必要的容量。

• capacity()：返回當前 vector 的容量。

• resize(x)：將 vector 的大小改為 \(x\)。若：
  把大小修改到大于當前容量，會把大小和容量都改到 \(x\)；
  把大小修改但不超過當前容量，只動大小不動容量。
  如果把大小改大，會在其之后加入 \(0\)；如果把大小改小，會刪掉多余的元素。

• reserve(x)：將 vector 的容量增加到 \(x\)。如果 \(\boldsymbol x\) 小于當前容量，則什么都不做。

• shrink_to_fit()：將當前 vector 的容量修改到和大小相同。

綜上所述，在這道題中，我們需要把當前 vector 的容量清空，我們該怎么做呢？設當前 vector 為 \(x\)。

1. vector<int>().swap(x)，意思是構造一個空 vector，將它和 \(x\) 交換。因為 swap() 可以同時交換大小和容量，且這個構造的 vector 會在使用后就被銷毀，所以我們便達到了目的。
2. x.clear(), x.shrink_to_fit() 意思是先清空大小，再將容量調整至和大小相同。這樣我們也達到了目的。

錯誤示范：

1. x.resize(0)：由于 resize() 只改大小不改容量，所以這樣寫和 x.clear() 沒有區別。
2. x.reserve(0)：由于 reserve() 只能增加容量，所以這樣寫等于沒寫。

deque / list

deque 也是支持常數級別隨機訪問的，但增刪元素為線性。list 支持常數增刪元素，但隨機訪問為線性。函數與 vector 差不多，但又有差異。

set / multiset / unordered_set / unordered_multiset

• 大家都會用的對數復雜度的 insert() 和 erase()。這倆函數其實都是有返回值的，insert() 函數返回一個 pair<iterator, bool> 其中前者為指向所插入元素（或原本就在容器里的元素）的迭代器，后者表示是否插入成功（set 中若已有元素會失敗）。如果傳的是元素，erase() 函數返回刪除元素的個數；如果傳的是迭代器，返回下一個元素的迭代器。

• 注意 multiset 的 erase() 函數會刪除當前鍵值的所有元素。

• 首尾迭代器方面和 vector 相同。

• count(x)、find(x)、lower_bound(x)、upper_bound(x) 大家都會用，注意除 count(x) 返回的是 \(x\) 的數量外，剩下的返回的都是迭代器。

• unordered 內部是用哈希表實現的，理論插入、刪除、查詢復雜度 \(O(1)\)，但容易被卡，詳見后文。

求交集/并集/差集/對稱差集（2024/10/16 upd.）

用法：前四個參數都是兩個集合首尾的迭代器，最后一個參數為 inserter(c,c.begin()) 的形式，其中 \(c\) 是輸出結果的 set。

注意，這些函數只能用于 STL，且使用前提是 STL 容器有序，所以它可以用于有序的 vector，但不能用于 unordered_set。

• set_intersection(a.begin(),a.end(),b.begin(),b.end(),inserter(c,c.begin())：求 \(a\) 和 \(b\) 的交集。
• set_union(...)：求并集。
• set_difference(...)：求差集。
• set_symmetric_difference(...)：求對稱差集。

map / unordered_map

• 其實也有 multimap 的，但是不常用。

• 與 set 同理，相當于給每個元素附帶一個別的值。其實用 map 最常用的就是像數組一樣的映射，也就是 [] 運算符。但注意，查詢一個元素是否存在不要用 []，而是要用 count() 函數。因為用 [] 如果不存在會新建一個元素反復使用會造成 TLE。

• 重載比較運算符（對于 set、multiset、map）：

struct cc {
	bool operator () (const int &a, const int &b) const {
		return a > b;
	}
};
set<int, cc> st;
map<int, int, cc> mp;

• 重載哈希函數（對于 unordered_set、unordered_multiset、unordered_map）：

先要說一下 unordered 系列容器的被卡問題，因為它們底層都是基于哈希表實現的，而 STL 自帶的哈希函數很史（優點是效率高），所以只需要頻繁插入一個特定素數的倍數就能制造哈希沖突，把哈希表卡到 \(O(N)\)。這個素數在 GCC 6 以前的編譯器上是 \(126271\)，在以后的編譯器上是 \(107897\)。
想要解決這個問題就是自己寫哈希函數。可以利用與時間有關的庫函數生成當前時間，然后把該值加入到哈希函數中，可以 100% 防止被卡。

struct hh {
	int operator () (const int &x) const {
		// 你的哈希函數 
	}
};
unordered_set<int, hh> st;
unordered_map<int, int, hh> mp;

有某些更好的哈希函數，比如：

const auto RAND = chrono::high_resolution_clock::now().time_since_epoch().count();
struct hh {
	int operator () (const int &x) const {
		return x ^ RAND;
	}
};

這是防止某些處心積慮的人卡 unordered_map 的，如果是 long long 類型，就寫成 return (x >> 32) ^ x ^ RAND;。但是，它無法使 pb_ds 中的哈希表走出困境。

更強的哈希函數（Codeforces 大佬推薦）：

const auto RAND = chrono::steady_clock::now().time_since_epoch().count();
struct hh {
    static int splitmix64(int x) {
		x += 0x9e3779b97f4a7c15;
		x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
		x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
		return x ^ (x >> 31);
	}
	int operator () (const int &x) const {
		return splitmix64(x + RAND);
	}
};

實測 gp_hash_table 加這個哈希函數跑到飛起。

2024/11/28 upd.

寫這句話的人完全是在胡扯。實際上在不卡哈希的情況下，手寫哈希函數的效率會慢 1.2 倍左右。除非你是在 CF 這種毒瘤云集的地方做題，否則不建議手寫哈希函數，甚至不建議用 pb_ds，一是沒有必要，二是可能有副作用。STL 中的東西能應付八成以上的情況，且 pb_ds 從來都不是一道題的必須。如果你非用 pb_ds 不可，只能說明你在亂搞。（逃

如果給 pair 寫哈希函數，只需給 first 和 second 都按你的哈希函數哈希一下，把后者的哈希值右移一位（看網上博客說的，不知道有什么意義），最后返回二者異或的值。

stack / queue / priority_queue

• stack 已不建議使用，建議使用數組模擬棧，常數小、靈活，關鍵是清空方便（stack 沒有自帶的 clear() 函數）。
• queue 的用途比 stack 廣，比用數組模擬好寫。筆者目前遇到的用數組模擬隊列只有在某些斜率優化 DP 中。
• priority_queue 直接用，自動排序還是方便。
• 它們的成員函數都是很樸素的一些 push()（C++11 后建議改為 emplace()）、pop()、empty()、size() 等，以及 top() 或 front() 訪問元素。

bitset

bitset 嚴格來說不屬于 STL，但它是包含在 #include <bits/stdc++.h> 中的。

首先要注意的是，隨機的、跳躍的訪問會拖慢 bitset 的效率，使之不如 bool 數組。所以圖論里常見的 \(\mathit{vis}\) 數組最好還是寫成 bool 數組的形式。

其余情況下，bitset 理論能把復雜度優化到 \(O(\frac nw)\)，其中 \(w\) 是計算機位數，一般是 \(32\) 或 \(64\)。關于 bitset 的詳細用法請自行 BDFS。

exSTL 之 pb_ds

大殺器。引用頭文件如下：

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp> // 用哈希表
#include <ext/pb_ds/tree_policy.hpp> // 用平衡樹
#include <ext/pb_ds/priority_queue.hpp> // 用堆
using namespace __gnu_pbds;

cc_hash_table / gp_hash_table

pb_ds 中的哈希表，實測后者比前者快。一般用于代碼卡常，以筆者當前經驗來看，拿 gp_hash_table 代替 unordered_map 準不會慢，前提是手寫哈希函數。

語法與 unordered_map 無異。

裸的 pb_ds 哈希表也是能被卡的（頻繁插入 \(2^{16}\) 的倍數），具體防卡方法上文有述。

tree

平衡樹，pb_ds 最為強悍之處。這篇博客講了其中一部分，下面再補充一些。

語法和 set 無異，可以實現 set / map 所有功能外加

• order_of_key(x)：返回 \(x\) 在平衡樹中的排名。
• find_by_order(x)：返回平衡樹中排名 \(x\) 的元素。
• join(b)：將平衡樹 \(b\) 合并到當前平衡樹，重新按照給定的比較函數排序。要求 \(\boldsymbol b\) 中的元素值域和 \(\boldsymbol a\) 中的元素值域不能重合。

  不僅僅是不能有相同元素。譬如，若 \(a=\{1,2,4\},b=\{3,5\}\)，則 \(a\) 和 \(b\) 同樣不能 join。

• split(v, b)：將當前平衡樹中 \(\le a\) 的元素保留到當前平衡樹，\(>a\) 的元素分裂到平衡樹 \(b\)。注意 \(\boldsymbol b\) 中原本的元素會被清空。

可以看出，pb_ds 中的平衡樹幾乎可以解決所有按鍵值分裂的平衡樹題目。

priority_queue

與 STL 中的 priority_queue 類似。

假設類型是 int，語法：__gnu_pbds::priority_queue<int,less<int>> q，后面的參數默認就是最快的。

容易發現的是，pb_ds 里的優先隊列和 STL 里的相比，重載運算符可以少寫一個參數，效率上其實差別不是很大。

但是，你以為這就完了嗎？好玩的地方才剛剛開始。

我們先來關注一下它的成員函數：

• STL 中的所有成員函數；
• modify(it,key)：把迭代器 \(\mathit{it}\) 位置的元素改成 \(\mathit{key}\)；
• erase(it)：刪除迭代器 \(\mathit{it}\) 位置的元素；
• join(b)：把優先隊列 \(b\) 合并進來并把 \(b\) 清空。

容易發現的是 pb_ds 里的優先隊列實現的是一個可并堆。十分好玩的一點是，這個可并堆的迭代器是點失效保證，也就是在修改容器但迭代器所指向的元素沒有被刪除時有效。干說有點抽象，我們來看一道例題：P11266 【模板】可并堆 2。

這題看似簡單，但如果不用 pb_ds 里的優先隊列貌似只能用左偏樹做。注意到 pb_ds 里的迭代器是點失效保證的，所以如果我們記錄下每個 \(a_i\) 的迭代器，然后把一個堆并入另外一個堆，迭代器依然是有效的。所以我們記錄每個隊列中元素的迭代器就可以巧妙地完成這個問題。

constexpr int MAXN=1e6+5;
int n,m;
__gnu_pbds::priority_queue<int,greater<int>>q[MAXN];
__gnu_pbds::priority_queue<int,greater<int>>::point_iterator it[MAXN];

int main(){
	n=read(),m=read();
	for(int i=1;i<=n;++i) it[i]=q[i].push(read());
	while(m--){
		int op=read();
		switch(op){
			case 0:{
				int x=read(),y=read();
				q[x].erase(it[y]);
				break;
			}case 1:{
				write(q[read()].top());
				break;
			}case 2:{
				int x=read(),y=read();
				q[x].join(q[y]);
				break;
			}default:{
				int x=read(),y=read(),z=read();
				q[x].modify(it[y],z);
				break;
			}
		}
	}
	return fw,0;
}

另：其實用 multiset 就能解決這個問題，感謝 LMX。

exSTL 之 rope

二殺器。不過目前還沒有使用它的實例，先咕著。

隨機化類

既是造數據的幫手，又是騙分的利器。

時間函數

一般用于初始化隨機種子，也用于對拍求程序運行時間、卡時、手寫哈希函數等。

clock 函數

用法：clock()，返回當前程序運行的毫秒數（Windows 下）。注意，不同系統得到的返回值單位不同，因此統一成秒的方法是：(double)clock() / CLOCKS_PER_SEC。大家都會用，不贅述了。

一般用于卡時、對拍。

time 函數

用法 time(0)，返回從 1970 年 1 月 1 日到現在的秒數，一般用于初始化隨機種子。但因為是秒級別的，所以一秒內生成的隨機數相同，會影響效率。

chrono 類

chrono 是 C++11 新增的一個時間類，功能強大，不過我目前只用它的兩個函數：

• chrono::steady_clock::now().time_since_epoch().count()
• chrono::high_resolution_clock::now().time_since_epoch().count()

網上很多文章都說后者是精度最高的時鐘，但實際上精度都能到納秒，根本不用追求二者的精度差異。何況這玩意還是看實現的，在我的電腦上，high_resolution_clock 直接被定義成了 system_clock 的別名。更多時候還是建議使用前者，因為前者產生 \(10^{14}\) 級別，而后者產生 \(10^{19}\) 級別，前者不太會產生溢出問題。具體還是看用途來決定使用哪個。

timeb 類

另一種初始化毫秒級別隨機種子的方法，注意在 Linux 下不能使用。

struct _timeb T;
_ftime(&T);
mt19937 wdz(T.millitm);

隨機化函數

大家都會使用 rand()，但是 Windows 下 rand() 的值域只有 \(32767\)。如果使用 rand() * rand() 的手法生成更大的隨機數，這樣生成的隨機數極不均勻。且眾所周知的種種原因，rand() 不再推薦使用。

mt19937

推薦使用的是 mt19937，它的優點無需更多贅述。直接定義 mt19937 能生成 unsigned int 范圍內的隨機數，定義 mt19937_64 能生成 unsigned long long 類型的隨機數。例：

mt19937 wdz;
cout << wdz() << '\n';

然而，你會發現這樣每次輸出的隨機數是相同的，因此需要初始化隨機種子。初始化方法：mt19937 wdz(1953615)，這樣就將 1953615 作為隨機化種子。和上面的時間函數結合，就是毫秒級別的隨機數種子。

uniform_int_distribution

眾所周知，用 wdz() % 1000000000 這樣的方法生成的隨機數是不均勻的，會偏小。這個函數可以生成真正均勻的隨機數。

用法：uniform_int_distribution<>(1, 1e9)(wdz)，可以生成均勻分布于 \([1,10^9]\) 的隨機整數。其中尖括號里不填表示 int 類型，需要 long long 就填成 long long 即可。中間的就填范圍，后面的 wdz 是一個 mt19937。

經過實測，這個函數的常數比較大，如果用在代碼里，請注意它的效率。

uniform_real_distribution

用法類似，給定的兩個邊界用于生成 \([a,b)\) 的隨機數，尖括號里填浮點數類型。一般用于模擬退火。

以 uniform 開頭的其他函數可以生成非均勻分布的隨機數，如正態分布等，用途不大。

隨機化算法

用于求解最優解問題的大殺器，也是求解部分期望題的最有效騙分手段。針對很遜的出題人，這種方法可以騙取極高的分數。隨機化算法的準確性依賴數據范圍，針對規模小的數據準確率很高。如果是用于求解期望題，則需要最終輸出的答案不超過兩位小數，準確率就非常高了。

首先是最常見的隨機化 + 卡時，這種無需多言，按照題意模擬，最后取最優解即可。

然后是高級一些的模擬退火，參見洛谷上的一篇專欄。

卡常類

收錄一些也不知有沒有用的卡常小寄巧。其中大多數應該都可以靠 O2 優化，按個人喜好。不按照效果排序。

• 輸入輸出優化，不再贅述。cout 時 endl 寫成 '\n'。

• 所有的 i++ 改為 ++i。據說是因為前者的底層實現不好，但 O2 應該能優化。

• 將簡單的 if 語句改為三目運算符或邏輯表達式，據說是因為 if 的常數大。這里重點說一下后者，我們知道 C++ 的邏輯運算符 && 和 || 是由執行的先后順序的，即從左到右執行。也就是說，如果前者已經足以讓這個表達式為真或假，就不會執行后面的語句。利用這個特性，我們就有：

  1. 所有的 if (a) b; 可以改為 a && b。
  2. 所有的 if (!a) b; 可以改為 a || b。
     這樣理論上能優化一些常數的，也可以用來壓行。需要注意的是，表達式 b 的返回值必須能轉為 bool 類型，所以我們可以用逗號分隔開，利用逗號表達式返回值為最后一項的特性即可。

• 盡量減少局部變量的定義，比如在循環內定義變量可以移到循環外面。

• 用 constexpr 關鍵字定義常量，可以促使該常量在編譯時計算。

• 各種 size 類函數盡量不要重復調用，比如盡量不要寫 for (int i = 0; i < s.size(); ++i)，因為它們的常數一般都不小，有些的復雜度甚至是線性的。

• 計數類題目的加法取模優化，即：a = (a + b) % p 改為 a = a + b >= p ? a + b - p : a + b。因為取模的效率很低，對于這種加法直接判斷會好很多。減法也是類似的，如 a = (a - b + p) % p 改為 a = a - b < 0 ? a - b + p : a - b。

• vector 的容量優化。前文提到過 vector 容量和大小的區別，vector 看似是動態的，實際上它每次加入元素時，如果當前容器的大小超過了容量，它就會重新申請內存，而這個申請內存的過程是很浪費時間的。所以對于已知的需要大量插入的 vector，合理地使用 reserve() 函數可以極大地優化它的常數。

位運算類

直接看這里。