一些注意事项

—— 简单题不 sb 是什么水平？

—— 国家队水平。

sb 错误

• 开 long long 时记得快读也要开 long long。

• 记得删调试信息，尤其是 cerr。

• 多测时要小心使用 memset。

• operator 前面记得加返回值类型名。（dev c++ 不报错不警告）

• 跑的很快可能是因为被优化了，因此不要用空循环测运行用时。

• （用于在线比赛）RE 可能是爆栈了。

• 不要假根号分治（可能大于 / 小于根号的同样可以处理小于 / 大于根号的）。

• 对常数有要求时应尽可能地避免复杂度瓶颈上的 push_back/emplace_back，解决方法有：在 push_back 前 reserve、使用 resize、使用传统数组等。

• for (auto element : container) 需要在原处修改时使用 auto & 而非 auto。

• 不要同时 vector<...> a(...) 和 a.push_back(...) 而导致数组长度翻倍且前一半是空的。

• q=0 不一定是不输出，例如题目要求输出答案的异或和时，就要输出 0。

• OI 赛制记得自己测极限数据（最大 & 最小）。

• 不要把动态开点线段树写成可持久化线段树（常数会大）。

• 无符号整型（如 container.size()）减去一个正数时需要留意，若不能保证结果非负，则需要将无符号整型显式转换为有符号整型再进行运算。

• 虽然不是很懂为什么，但用 vector 写矩阵貌似非常慢。可能是计算过程中要频繁地创建新 vector 吧。

sb 想不到

• 计数 → 什么是重复的，什么是相同的。要做到不重不漏

• 最优化 → 什么是不优的，什么是不劣的。

• 要是怎么样就好了 → 能不能转化成这样。

• 存在反例 → 反例能否特殊处理。

• 只用管大小而不关心具体值 → 从小到大、从大到小考虑 / 二分答案转成 01。

• 构造最小值 → 找到一个较紧的下界，构造出下界（或者构造出一个方案，证明它是下界）。

• 分很多种奇奇怪怪的情况讨论时，可以想一想这些情况的补集。

• 有多次修改的题，可以考虑没有修改怎么算以及如何处理修改，而不一定要把初始状态当作若干次修改。

• 多次二分时想一想能不能用双指针。

• 成双成对的元素，在一起怎么样，不在一起怎么样，经常可以用随机数异或来处理。

• 把整个序列分成若干段，每段求一个值再加起来求最值，暴力是 DP，经常可以用决策单调性优化。

• 图论相关问题（包括树上问题）可以考虑点和边互相转化。

• 能够卷积时想一想能不能直接背包。

• 求生成函数然后带值进去求答案，可以过程中直接算点值。

• 无法继续优化往往是因为求了不必要的东西。

• 路径加单点求值可以树上差分 + 树状数组，不需要树剖/LCT。

• 不要使用动态开点线段树来求不带修的区间和，在对常数有要求时也不要使用 map，而应使用 vector + 二分 + 前缀和。

• 多次求矩阵快速幂乘一个向量时，可以预处理矩阵的幂（一次，二次，四次，八次…），然后每次都用矩阵乘向量（从右向左依次算），这样预处理复杂度是 $O(n^3\log k)$，单次询问复杂度是 $O(n^2\log k)$。更一般地，求多个矩阵（每个矩阵都是已知的）的积乘上一个向量时，可以利用结合律每次都用矩阵乘向量。