通用hash方法 由于unordered_map, unordered_set等无序关联式容器内置的hash函数有限，pair，tuple，array等类型无法作为key值，需要自己写hash函数（值得一提的是bitset有特化的hash函数可以直接作为键值），这些类型是可以可以作为关联式容器例如set、map的key值的（vector也可以），但复杂度多一个log，因此记录一个比较简单通用的hash方法。 适用于 2022-03-21 常数优化 hash
吸氧火车头 收集的比较有效的火车头，实际比赛不建议用 1234#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize("inline")#pragma GCC optimize("-fgcse-lm") 2022-03-21 常数优化
树上启发式合并 启发式算法是指基于人类的经验和直观感觉，对一些算法的优化，最常见的有并查集的按秩合并，即对于两个大小不一样的集合，我们总是将小的集合合并到大的集合中，让高度小的子树成为高度大的树的子树，这个优化称为启发式算法，通过启发式优化，可以将部分树上问题的复杂度为$O(n^2)$的算法优化成$O(nlog_2n)$。树上启发式合并的详细介绍及复杂度证明见OI Wiki：树上启发式合并。 结合LeetCode 2022-03-21 启发式合并
普通线段树（带懒标记） 主要功能是支持区间修改和区间查询，核心思路是添加一个懒标记，延迟传播修改信息，查询到某个区间时才把其祖宗节点的懒标记代表的修改信息传播下来，借此做到log级别的时间复杂度 该模板区间上的懒标记代表不包括该区间的所有子节点的修改信息 123456789101112131415161718192021222324252627282930313233343536373839404142434445464 2022-03-21 线段树
快速输入输出 实测在部分输入输出数据量极为恐怖的题中，即使是scanf和printf速度也略显不足; 因此抄了份快速输入输出的模板，write默认是以换行符结尾，若需要空格，write(x, 32)即可，因为换行符的ascii码是10，而空格的ascii码为32； 另外，由于是模板函数，因此也可以支持__int128类型的输入输出。 123456789101112131415161718template< 2022-03-21 常数优化
差分约束 对于一系列形如$x_i \leq x_j + c_k$的不等式组，其中$x_i$走到$x_j$都是自变量，$c_k$是一个常数。 考虑我们的最短路算法，假设从$j$走到$i$存在一条长度为$c$的边，那么跑完最短路算法后，就必然有以下三角不等式成立：$$dist[i] \leq dist[j] + c$$原因很简单，因为当$dist[i] > dist[j] + c$时，$dist[i] 2022-03-21 差分约束
通过位运算进行子集枚举 常规枚举子集可以用回溯算法，缺点是代码相对更长、常数更高，因此我们可以采用位运算的方法枚举某个s（用二进制表示状态）的子集，好处在于代码非常好写，常数低，容易结合具体操作。 枚举s的子集 12345int n = s.size(), tot = (1 << n) - 1;for(int i = tot; i; i = tot & (i - 1)) { //具体操作&# 2022-03-21 位运算
动态开点线段树（带懒标记） 普通带懒标记的线段树的节点是提前建好的，参考普通线段树模板中的build函数，缺点在于空间开销比较大（4倍空间），对于一些查询范围很大，而查询次数有限的题，由于空间限制无法采用普通带懒标记的线段树。 因此大佬们发明了动态开点的线段树，与普通线段树相比，动态开点线段树最大的特点就是他的点是需要的时候才创建，节点的左右儿子编号并非2u和2u + 1，因此我们每次在查询和修改时将儿子信息也一并传入即可。 2022-03-21 线段树
主席树（可持久化线段树） 主席树、又称为可持久化线段树，实际上是记录了每一次更新时的版本信息，目前接触到的题型基本上都是结合离散化搞，最经典的用法是求区间第K大/小的数 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686 2022-03-21 线段树