奇技淫巧

忆雏闲 · 2025-6-1 18:39:26

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。

剩下的个人感觉不常用了，可以自己打开头文件看。
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 库中定义了很多常量，使用方法：

代码开头在引用头文件前必须写一句 #define _USE_MATH_DEFINES，不写是用不了的，也可以写头文件里剩下的那几个；
然后就可以使用里面的各种常量了。下面直接放头文件，注意有第二个下划线的是除以的意思，如 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)。
遍历范围为整个数组。

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 库

<ul>exp2(x)：返回 \(2^x\)。<blockquote>
如果 \(x\) 是整数，不如用 1 b; }};set st;map mp;[/code]

重载哈希函数（对于 unordered_set、unordered_multiset、unordered_map）：

先要说一下 unordered 系列容器的被卡问题，因为它们底层都是基于哈希表实现的，而 STL 自带的哈希函数很史（优点是效率高），所以只需要频繁插入一个特定素数的倍数就能制造哈希冲突，把哈希表卡到 \(O(N)\)。这个素数在 GCC 6 以前的编译器上是 \(126271\)，在以后的编译器上是 \(107897\)。
想要解决这个问题就是自己写哈希函数。可以利用与时间有关的库函数生成当前时间，然后把该值加入到哈希函数中，可以 100% 防止被卡。

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

复制代码

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

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

复制代码

这是防止某些处心积虑的人卡 unordered_map 的，如果是 long long 类型，就写成 return (x >> 32) ^ x ^ RAND;。但是，它无法使 pb_ds 中的哈希表走出困境。
更强的哈希函数（Codeforces 大佬推荐）：

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

复制代码

实测 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 中的。
首先要注意的是，随机的、跳跃的访问会拖慢 bitset 的效率，使之不如 bool 数组。所以图论里常见的 \(\mathit{vis}\) 数组最好还是写成 bool 数组的形式。
其余情况下，bitset 理论能把复杂度优化到 \(O(\frac nw)\)，其中 \(w\) 是计算机位数，一般是 \(32\) 或 \(64\)。关于 bitset 的详细用法请自行 BDFS。
exSTL 之 pb_ds

大杀器。引用头文件如下：

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

复制代码

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 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\) 的迭代器，然后把一个堆并入另外一个堆，迭代器依然是有效的。所以我们记录每个队列中元素的迭代器就可以巧妙地完成这个问题。
[code]constexpr int MAXN=1e6+5;int n,m;__gnu_pbds::priority_queueq[MAXN];__gnu_pbds::priority_queue::point_iterator it[MAXN];int main(){ n=read(),m=read(); for(int i=1;i

账号		自动登录	找回密码
密码			立即注册