# CP-template **Repository Path**: intirain/CP-template ## Basic Information - **Project Name**: CP-template - **Description**: No description available - **Primary Language**: Unknown - **License**: Not specified - **Default Branch**: main - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2024-07-25 - **Last Updated**: 2024-07-25 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # CP-template C++ template files for competitive programming. #### 1.模板库特点： 1. ##### 兼容性高。 支持 `gcc` ，`clang` ，`MSVC` 等不同编译器，`C++11` 之后可以使用。 2. ##### 使用方便。 `FOR` 宏定义？ `i64` 缩写？编程老手都认识？ `No` ！本模板库中，不会使用这些花里胡哨的缩写，也不会假定使用者是老手。本模板，让任何码风的人都不会感到不适应。 各个模板之间，尽量减少依赖关系，代码界限分明，在复制粘贴、提交代码时十分清晰便捷。 在最新版本的 `TEST` 文件夹里，提供了本地运行代码，以及在若干 `oj` 题目上提交时的代码。 3. ##### 封装性好。 模板往往以类的形式存在，通过成员方法来进行操作；在遇到需要同时建立多个树状数组、多个线段树等问题时，可以轻松适应。 4. ##### 拓展性好。 可以在当前模板的基础上进行再次封装，例如 `SqrtTree` 就是在 `CatTree` 的基础上封装而成的。 5. ##### 零成本抽象。 这可以说是最重要的一点，很多写算法模板库的人，写出来的模板非常狭隘，稍微一换场景就会损失效率。比如设计平衡树，结果直接默认写成 `map` ，那在遇到要以 `set` 处理的问题时，显然就要白白添加一个没用的 `value_type` ，这是本模板库不能接受的。本模板库一定会写成既可以拓展为 `set` 也可以拓展为 `map` 且均为最佳效率的形式。 #### 2.设计原则： 1. `C++ style, not C style` 。 2. 代码格式化: ``` { BasedOnStyle: LLVM, UseTab: Never, IndentWidth: 4, TabWidth: 4, BreakBeforeBraces: Attach, AllowShortIfStatementsOnASingleLine: true, IndentCaseLabels: true, ColumnLimit: 0, AccessModifierOffset: -4, NamespaceIndentation: All, FixNamespaceComments: false ,AllowShortCaseLabelsOnASingleLine: true,AllowShortLoopsOnASingleLine: true,AllowShortBlocksOnASingleLine: true} ``` 3. 文件宏命名为：双下划线 + `OY` + 双下划线 + 模板名全称大写 + 双下划线 模板参数命名为：大写每个单词首字母； 类命名为：大写每个单词首字母； 类外的编译期常量命名为：全大写+下划线分割； 类内的编译期常量命名为：全小写+下划线分割； 成员变量命名为：`m` +下划线分割单词 成员函数命名为：下划线分割单词 静态变量命名为： `s` +下划线+下划线分割单词 形式参数命名为：下划线分割单词 4. 对不保证隐式类型转换成功的场景，使用显式类型转换。 如果代码出现 `bug` 或者设计问题，欢迎指出 #### 3.优秀的执行效率： ​ 本模板库的数据结构，拥有极其优秀的运行速度。例如： ​ 截止 `2024.04.14`，最快的 `K` 短路 https://www.luogu.com.cn/problem/P2483 ​ 截止 `2024.04.14`，最快的虚树 https://www.luogu.com.cn/problem/P2495 ​ 截止 `2024.04.14`，最快的区间排序线段树 https://www.luogu.com.cn/problem/P2824 ​ 截止 `2024.04.14`，最快的带懒更新的可并堆 https://www.luogu.com.cn/problem/P3261 ​ 截止 `2024.04.14`，最快的树上线性基 https://www.luogu.com.cn/problem/P3292 ​ 截止 `2024.04.14`，最快的带懒更新的线段树 https://www.luogu.com.cn/problem/P3373 ​ 截止 `2024.04.14`，最快的类树状数组结构 https://www.luogu.com.cn/problem/P3374 ​ 截止 `2024.04.14`，最快的最近公共祖先在线查询 https://www.luogu.com.cn/problem/P3379 ​ 截止 `2024.04.14`，最快的回滚并查集 https://www.luogu.com.cn/problem/P3402 ​ 截止 `2024.04.14`，最快的乘法逆元 https://www.luogu.com.cn/problem/P3811 ​ 截止 `2024.04.14`，最快的静态区间最值查询 https://www.luogu.com.cn/problem/P3865 ​ 截止 `2024.04.14`，最快的李超线段树 https://www.luogu.com.cn/problem/P4097 ​ 截止 `2024.04.14`，最快的 `FMT/FWT` https://www.luogu.com.cn/problem/P4717 ​ 截止 `2024.04.14`，最快的 `2-SAT` https://www.luogu.com.cn/problem/P4782 ​ 截止 `2024.04.14`，最快的类欧几里得算法 https://www.luogu.com.cn/problem/P5170 ​ 截止 `2024.04.14`，最快的回滚 `KMP` https://www.luogu.com.cn/problem/P5287 ​ 截止 `2024.04.14`，最快的线性基线段树 https://www.luogu.com.cn/problem/P5607 ​ 截止 `2024.04.14`，最快的 `Stoer-Wagner`算法 https://www.luogu.com.cn/problem/P5632 ​ 截止 `2024.04.14`，最快的动态树 https://www.luogu.com.cn/problem/P5649 ​ 截止 `2024.04.14`，最快的子序列自动机 https://www.luogu.com.cn/problem/P5826 ​ 截止 `2024.04.14`，最快的笛卡尔树 https://www.luogu.com.cn/problem/P5854 ​ 截止 `2024.04.14`，最快的势能线段树 https://www.luogu.com.cn/problem/P6242 ​ 截止 `2024.04.14`，最快的点双连通分量 https://www.luogu.com.cn/problem/P8435 ​ 截止 `2024.04.14`，最快的边双连通分量 https://www.luogu.com.cn/problem/P8436 ​ 截止 `2024.04.14`，最快的最小树形图算法 https://www.luogu.com.cn/problem/U210116 ​ 截止 `2024.04.14`，最快的 `GCD` 卷积 https://www.luogu.com.cn/problem/U151263 ​ 截止 `2024.04.14`，最快的树状数组 https://www.luogu.com.cn/problem/U187320 ​ 截止 `2024.04.14`，最快的势能线段树 https://uoj.ac/problem/170 ​ 截止 `2024.04.14`，最快的二维树状数组 [https://loj.ac/p/133](https://loj.ac/p/133)，[https://loj.ac/p/134](https://loj.ac/p/134)，[https://loj.ac/p/135](https://loj.ac/p/135) ​ 截止 `2024.04.14`，最快的二维 `ST` 表 http://acm.hdu.edu.cn/showproblem.php?pid=2888 ​ 由于这样的例子实在太多，故只选最具有代表性的模板列出。 #### 4.力扣输入输出模板使用方法： 1. 目前支持的编译器有 `clang` / `gcc` / `MSVC` 。 2. 包含 `LeetcodeIO.h` 头文件； 3. 在包含头文件之前，加一行 `#define OY_LOCAL` 作为本地的标志；（也可以在编译参数里加 `-DOY_LOCAL`） 4. 在运行目录下放入 `in.txt` 和 `out.txt` 作为输入输出文件；如果找不到运行目录，可以随便输出一个字符串，看看 `out.txt` 生成到了哪里。 5. `Solution` 类的使用：需要在第二行注册要运行的成员方法名； 6. 自定义 `Class` 类的使用：需要在第一行注册类名+构造函数的所有参数类型；需要在第二行注册类名+所有要用到的成员方法名 使用时可以参考两张 `png` 图片示例。 #### 5.FAQ 1. 我的编程环境非常老旧，看到你的模板库代码花里胡哨的，能运行起来吗？ 本模板库现已放宽对语言环境的要求，绝大多数模板， `gcc` 和 `clang` 在 `C++11` 之后均可使用； `MSVC` 在 `C++14` 之后均可使用（暂无 `C++11` 测试环境）。只要你的 `C++` 语言标准在 `C++11` 之后，均可以使用我的模板库。 2. 在很多模板里，看到 `MAX_NODE` 参数，这是什么意思？ 在平衡树、堆、动态开点线段树中，往往需要动态增加结点；往往这些数据结构的不同实例对象还可以互相合并。此时有两种设计方案：用指针表示结点；用数组下标表示结点。如果使用前者方案，指针是全局的概念，所以不同实例对象可以成功合并；但是结点的大小较大，占用空间较多。如果使用后者方案，数组下标是一个针对某个数组的概念，如果两个平衡树的结点是从两个不同的数组里分配的，那么就没有办法进行合并。 经过权衡，采用后者方案：用数组下标表示结点。这就要求存在一个全局的数组，从这个数组里向不同的实例对象分配结点；在合并时，每个结点里保存的左孩子、右孩子等下标可以保持原有的意义，而不至于无意义。 只要看到类内有 `s_buffer` 的存在，即表示有内存池。 3. 在各种数据结构里，填写的 `MAX_NODE` 是否越大越好？如果是多组测试，是否每组测试重新构造一个数据结构对象就会触发 $O(MAXNODE)$ 的初始化导致超时？ 以下回答针对你的结点类型为平凡类型的情况（无构造函数，无初始值）。 `MAX_NODE` 相关联的是结点内存池的大小，所以并不会出现每次构造一个数据结构对象，就导致内存池初始化的情况。 `MAX_NODE` 并非越大越好，当 `MAX_NODE` 过大时，编译可能会失败。只要编译能通过，那么在此范围内 `MAX_NODE` 多大都没关系，也不会有任何的时间开销。 4. 我用整数做平衡树结点键值跑得非常快；换成 `std::string` 做平衡树结点键值，为什么程序突然变得很慢？甚至在很小的样例上都很慢？ 由于模板库内使用静态变量做内存池，静态变量某种意义上就是全局变量，所以在程序启动时就会对所有的结点进行初始化。而 `std::string` 对象即使是空的，也存在初始化代价；如果 `MAX_NODE` 过大，就会占用很长时间。 一般来说，推荐使用平凡类型作为结点的成员变量。由于 `C++` 中，平凡类型的全局变量、静态变量初始化不消耗运行时，所以当你的数据结构的结点类型为平凡类型时，即使开再大的内存池也不会产生一丁点的运行时间。反之，如果你给结点设置了构造、析构，或者给某个成员变量设置了初始值，那么内存池的初始化就会占用时间。 5. 为什么在 `oj` (主要指 `codeforces` ) 提交平衡树代码时，提示如下？ ``` Can't compile file: Compiled file is too large ``` 首先需要知道，我的平衡树模板通过类似于 `MAX_NODE` 这样的模板参数控制一个模板最大的数组空间。这种方式产生的静态数组，并非是在运行期在堆上申请的，而是在编译时直接占用程序体积。 而一些平台，例如 `codeforces` 对生成的程序大小有限制，有时候 `MAX_NODE` 过大，会生成超出大小限制的程序而无法通过编译。此时问题很好解决，将 `s_buffer` 从结点数组类型修改为结点指针类型，然后将类外的 `s_buffer` 初始化改写为 `s_buffer = new 【结点类型】[MAX_NODE]` 即可。 例如，如果想声明一个普通平衡树，且最多可能插入二百万个元素，则需要声明如下类： `OY::AVLMultiset, 2000000>` 。当 `MAX_NODE = 2000000` 时，平衡树因为 `MAX_NODE` 过大而无法通过 `codeforces` 编译，则需要做如下修改： 第 `195` 行修改为 ``` static node *s_buf; ``` 第 `507` 行修改为 ``` typename Tree::node *Tree::s_buf = new typename Tree::node[MAX_NODE + 1]{}; ``` 此时即可通过 `codeforces` 编译。 6. 既然不会反复初始化内存池，那么多组数据之间是否会产生影响？ 不会。内存池里的结点只会被使用一次，上一组的数据使用的结点不会在下一组数据里被复用。 7. 线段树只能有求和的功能吗？ 本模板库非常重视模板的泛化程度，所以各种数据结构均支持通过传递运算符实现自由的操作。例如，对于线段树来说，可以传递 `lambda` 定义运算符来重载树中的信息聚合运算；或者通过定义一个结构体，并重载其括号运算符，达到同样的效果。其他的容器也往往如此。 8. 线段树模板参数一大堆，填写起来老是报错？连类型名字都不能完整写出来该怎么办？ 为了防止定义各种千奇百怪运算符的使用者在使用模板时，因为无法描述出模板的完整类型名称而困扰，所以特意编写了 `make_` 系列函数。如同 `std::make_pair` 以及 `std::make_tuple` 一般，只需要填写少量参数即可创建出复杂类型的模板。例如， `make_SegTree` 可以用来创建线段树；只要打出 `make_SegTree` 之后跟随 `IDE` 的智能提示进行相应的填写即可。 9. 用 `make_SegTree` 可以创建一颗线段树；但是如果我要在 `std::vector` 里存放十颗线段树，我还是得把类型全称写出来，可是我写不出来，怎么办？ 既然用 `make_SegTree` 可以创建出一颗线段树，那么可以用 `using NickName = decltype(make_SegTree<...>(...));` 来捕获这棵树的类型，并给它起个别名。接下来即可用 `std::vector` 的方式存储十颗线段树。 10. 为什么我用 `make_STTable(10, std::min)` 创建一个最小值表没问题，用 `make_STTable(10, std::max)` 创建一个最大值表没问题，但是我同时把两句代码写出来，表就出错了？ 本模板库的容器，以类型作为两种容器的区别特征；而 `std::min` 和 `std::max` 的类型相同，所以会把两个容器视为同一种容器。换句话说，后一个容器传入的函数指针会把前一个容器的函数指针覆盖掉，导致功能紊乱。 一般而言，本模板库不推荐使用函数指针作为操作符的容器；使用匿名函数作为操作符的容器，运行效率更高，也减少了出错的概率。