注意事项

负数 >> 1 和 / 2 不同，右移是向下取整，除法是向零取整。e.g. (-5) >> 1 = -3, (-5) / 2 = -2。

pb_ds 库

所有数据结构都在 __gnu_pbds 命名空间。

哈希表

头文件：

1 2	#include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/hash_policy.hpp>

定义：

拉链法处理冲突 cc_hash_table<key_type, value_type> hash_name
探测法处理冲突 gp_hash_table<key_type, value_type> hash_name（较快）

成员函数：

hash_name[key] 重载中括号运算符访问 value 值的引用，若 value 值不存在则新开辟空间。
iterator find(key_type num) 返回按 key 查找到的 value 值的迭代器，未找到返回 hash_name.end()。

平衡树 [UNFINISHED]

咕

堆

头文件：

1	#include <ext/pb_ds/priority_queue.hpp>

定义：

priority_queue<value_type, comp_struct, heap_tag> queue_name，尖括号中分别是元素类型、比较运算、自定义堆类型。堆的类型有：

配对堆	斐波那契堆	二项堆	二叉堆
`pairing_heap_tag`	`thin_heap_tag`	`binomial_heap_tag`	`binary_heap_tag`

使用合并的时候使用 pairing_heap_tag，做 Dijisktra 的时候使用 thin_heap_tag。

成员函数：

push
pop
top
join

C++ 语法

lambda 函数 & lambda 表达式

需要 C++11 及以上标准。

格式为 [capture](parameters) -> return_type {body}，其中圆括号和返回值可以省略。

示例：[](int x, int y) -> int { int z = x + y; return z; }。

capture	说明
`[]`	未定义变量。试图在 lambda 内使用任何外部变量都是错误的
`[x, &y]`	x 按值捕获，y 按引用捕获
`[&]`	用到的任何外部变量都隐式按引用捕获
`[=]`	用到的任何外部变量都隐式按值捕获
`[&, x]`	x 显式地按值捕获，其它变量按引用捕获
`[=, &z]`	z 按引用捕获，其它变量按值捕获

tuple 库

使用需 #include <tuple> + C++11 及以上标准。

创建：std::tuple<...> tuple_name 或 auto tuple_name = return std::tie(...);。

取值：std::tie(...) = tuple_name;。

函数名称	返回值
`std::tuple make_tuple(...)`	创建一个 tuple 对象，其类型根据各实参类型定义
`std::get<int num>(std::tuple tuple_name)`	获取第 num 个元素的引用，从 0 开始编号
`std::get<typename>(std::tuple tuple_name)`	获取类型为 typename 的元素，要求 tuple 中只有一个这样的元素
`std::tuple_cat(...)`	返回一个由括号中内容（tuple / pair）拼接成的 tuple 对象

比较运算按照从前到后的优先级逐个比较。

sort & merge

partial_sort(begin, middle, end, (cmp)) 使 $[\text{begin},\text{middle})$ 最小且有序。
stable_sort(begin, end, (cmp)) 稳定性排序。
merge(a.begin, a.end, b.begin, b.end, res.begin, (cmp))。

lower_bound & upper_bound

lower_bound(begin, end, num) 从数组的 $\text{begin}$ 位置到 $\text{end}-1$ 位置二分查找第一个 大于或等于 $\text{num}$ 的数字，找到返回该数字的地址，不存在则返回 $\text{end}$ 。
upper_bound(begin, end, num) 从数组的 $\text{begin}$ 位置到 $\text{end}-1$ 位置二分查找第一个大于 $\text{num}$ 的数字，找到返回该数字的地址，不存在则返回 $\text{end}$ 。

通过返回的地址减去起始地址 $\text{begin}$ ，得到找到数字在数组中的下标。

cctype 库

使用需 #include <cctype> 。

函数名称	返回值
`isalnum()`	如果参数是字母数字，即字母或者数字，函数返回 true
`isalpha()`	如果参数是字母，函数返回 true
`iscntrl()`	如果参数是控制字符，函数返回 true
`isdigit()`	如果参数是数字（0 ~ 9），函数返回 true
`isgraph()`	如果参数是除空格之外的打印字符，函数返回 true
`islower()`	如果参数是小写字母，函数返回 true
`isprint()`	如果参数是打印字符（包括空格），函数返回 true
`ispunct()`	如果参数是标点符号，函数返回 true
`isspace()`	如果参数是标准空白字符，如空格、换行符、水平或垂直制表符，函数返回 true
`isupper()`	如果参数是大写字母，函数返回 true
`isxdigit()`	如果参数是十六进制数字，即 0 ~ 9、a ~ f、A ~ F，函数返回 true
`tolower()`	如果参数是大写字符，返回其小写，否则返回该参数
`toupper()`	如果参数是小写字符，返回其大写，否则返回该参数

函数原型均为 int is____(int)。

g++

编译与生成文件

-o filename 制定目标名称，e.g. g++ a.cpp -o a.exe。
-O0 / -O1 / -O2 / -O3 编译器的优化选项的 4 个级别。
-pg 产生供 gprof 剖析用的可执行文件。
-S 生成汇编代码，e.g. g++ -S a.cpp。

错误与告警选项

-Wall 一般使用该选项，允许发出 GCC 能够提供的所有有用的警告。
-Wextra 开启额外警告。
-Wno-deprecated-register
-Wshadow 当一个局部变量遮盖住了另一个局部变量，或者全局变量时，给出警告。
-Wpointer-arith 对函数指针或者 void * 类型的指针进行算术操作时给出警告。
-Wcast-qual 当强制转化丢掉了类型修饰符时给出警告。
-Wunreachable-code 如果编译器探测到永远不会执行到的代码，就给出警告。
-werror 把所有警告转换为错误，以在警告发生时中止编译过程。
-w 关闭所有警告，建议不要使用此项。

扩大栈空间

Windows 下，在编译选项中加入 -Wl,--stack=536870912。数字可自行选择，单位为字节（B）。
Linux 下，在终端中输入 ulimit -v 524288 和 ulimit -s 524288。数字可自行选择，单位为千字节（KiB）。也可以将数字替换为 unlimited（无限制）。

消毒水 Sanitizer

-fsanitize=address AddressSanitizer：检查内存使用。包括数组越界、解引用悬垂指针等错误。
fsanitize=undefined UndefinedBehaviorSanitizer：检查未定义行为。包括按位位移溢出、使用空指针等错误。可在运行程序时 UBSAN_OPTIONS=print_stacktrace=1 环境变量来打印出错位置的调用栈。
-fsanitize=leak LeakSanitizer：检查内存泄漏。其实现原理与 AddressSanitizer 不同。注意 Windows 下尚不支持 LeakSanitizer。
-fsanitize=memory MemorySanitizer：检查使用未被初始化的值的错误。可在编译选项中加入 -fsanitize-memory-track-origins 环境变量来追踪未被初始化的值的每一次移动。注意 GCC 并没有集成这个工具，所以你只能在 Clang 中使用它。
-fsanitize=thread ThreadSanitizer：检查多线程代码中的数据竞争。由于 OI 中不涉及多线程程序，因此不讨论 ThreadSanitizer 相关内容，你也不需要在 OI 中使用它来检查你的代码。

当前公布的 NOI Linux 2.0 的 GCC 版本为 9.3.0，其自带有除 MemorySanitizer 外的所有 Sanitizer。OI 中遇到『段错误』时，可以在编译选项中加入 -fsanitize=address,undefined,leak 参数，来获取帮助。请注意，开启 Sanitizer 后的程序效率并不具有参考性！

参考资料：Awesome sanitizers (by @yurzhang)。