算法优化中的常数优化技巧
在程序设计竞赛中，面对时间与空间限制极为严苛的题目时，仅靠算法复杂度优化往往不足以通过全部测试点。此时，对代码执行效率进行精细调整——即"卡常"——成为关键手段。尤其对于复杂度接近理论极限的算法（如分块、莫队、树套树等），常数优化直接影响能否通过时限。
通常，当题目数据规模不大但常数较高，或存在大量重复操作时，即使时间复杂度看似合理，也可能因常数过大而超时。例如，在某些情况下，一个 $O(n^2)$ 的解法在 $n=10^4$ 时仍能通过，这正是由于实际运行中每轮操作开销极小。
核心优化策略
- 聚焦瓶颈部分：优先优化最耗时的代码段，尤其是那些虽然复杂度高但实际执行次数多的部分。避免在 $O(n\log n)$ 算法中过度优化 $O(n)$ 段落。
- 使用内联函数：将频繁调用的小函数标记为
inline，减少函数调用开销。 - 替换递归为循环：递归调用涉及栈帧创建与维护，通常比循环慢。对于可迭代结构（如遍历树、图），尝试改写为非递归形式。
- 简化输入处理：若已知输入无负数，可移除快读中关于符号的判断逻辑，提升速度。
- 消除冗余计算：避免重复计算相同表达式，必要时以空间换取时间（如预处理数组）。
- 自定义容器替代标准库：如手动实现
stack、queue、deque，避免标准模板带来的额外开销；对于vector可考虑用邻接表等更高效结构替代。 - 清理调试残留：删除未被条件覆盖的输出语句或调试打印，哪怕不执行也会增加分支判断开销。
- 改变搜索方式：将深度优先搜索（DFS）改为广度优先搜索（BFS）有时可显著提速；对树形结构多次自底向上处理时，预先计算拓扑序并逆序遍历，避免递归开销。
典型高难度卡常题例
- P4135 作诗：未优化的分块会同时遭遇时间与空间瓶颈。
- P4718 Pollard-Rho 模板：极端卡时间，要求极致优化。
- P3527 MET-Meteors：整体二分若未精简，极易超时。
- P3380 二逼平衡树：树套树结构下，Splay 实现极易被卡。
- P3759 不勤劳的图书管理员：Splay 被严格卡常，需改用树状数组套线段树。
另类挑战：空间卡常
少数题目不仅卡时间，还对内存极其敏感。例如：
应对空间限制的方法包括：
- 延迟计算：不预先存储中间结果，需要时再现场计算。
- 缩小数据类型：将
int改为short，布尔数组使用bitset压缩存储。 - 算法重构：如用线段树替代 ST 表，或用 K-D Tree 替代树套树结构。
常用快速读入模板
template<typename T> inline void fast_read(T &x) {
x = 0;
char c = getchar();
bool is_negative = false;
while (!isdigit(c)) {
if (c == '-') is_negative = true;
c = getchar();
}
while (isdigit(c)) {
x = x * 10 + (c - '0');
c = getchar();
}
if (is_negative) x = -x;
}
快速输出模板（备选）
template<typename T> inline void fast_write(T x) {
short stack[30];
int top = 0;
if (x < 0) {
putchar('-');
x = -x;
}
do {
stack[++top] = x % 10;
x /= 10;
} while (x);
while (top) {
putchar('0' + stack[top--]);
}
}
