排序
竞赛中几乎总是用库函数：
- C++：
sort(a, a+n)平均 $O(n \log n)$ - 需要稳定排序：
stable_sort - 自定义比较：
sort(v.begin(), v.end(), [](const auto& x, const auto& y) { return x.second < y.second; });
离散化
值域很大但个数少时，把值映射到 $1\sim k$：
vector<int> all = a;
sort(all.begin(), all.end());
all.erase(unique(all.begin(), all.end()), all.end());
int id = lower_bound(all.begin(), all.end(), x) - all.begin();
二分答案
当「判定是否可行」比「直接求最优」容易时：
- 确定答案区间 $[L, R]$
while (L < R)取mid，若可行则收缩一侧- 注意边界：
mid = (L + R + 1) / 2避免死循环
二分查找
在有序数组上：
lower_bound：第一个 $\ge x$upper_bound：第一个 $> x$- 个数：
upper_bound - lower_bound
三分
单峰函数求极值：在 $[L,R]$ 上取三等分点比较，适用于凸函数或明确单峰的性质题。
计数排序 / 基数排序
值域小（如 $10^6$ 以内）时可 $O(n)$ 或接近线性，配合离散化使用。
例题
例 1：砍树 / 木材加工（二分答案）
有 $n$ 棵树，高度 $h_i$，要得到至少 $m$ 米木材。设统一砍到高度 $H$，可得 $\sum \max(0, h_i - H)$。$H$ 越大木材越少，二分 $H$，每次 $O(n)$ 检查是否 $\ge m$。复杂度 $O(n \log \max h)$。
例 2：逆序对 / 排名（离散化 + 树状数组）
值域 $10^9$ 但只有 $n$ 个数，先排序去重得到排名 id，再在树状数组上从左到右插入，查询比当前值小的个数即为逆序对贡献。体现「排序 + 离散化」组合拳。