Skip to content

old-yan/CP-template

BranchesTags

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

340 Commits
.vscode
.vscode
 
 
DS
DS
 
 
GRAPH
GRAPH
 
 
IO
IO
 
 
MATH
MATH
 
 
MISC
MISC
 
 
STR
STR
 
 
TEST
TEST
 
 
TREE
TREE
 
 
.gitignore
.gitignore
 
 
README.md
README.md
 
 

Repository files navigation

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/134，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<int, std::less<int>, 2000000> 。当 MAX_NODE = 2000000 时，平衡树因为 MAX_NODE 过大而无法通过 codeforces 编译，则需要做如下修改：

    第 195 行修改为

    static node *s_buf;

    第 507 行修改为

    typename Tree<NodeWrapper, MAX_NODE>::node *Tree<NodeWrapper, MAX_NODE>::s_buf = new typename Tree<NodeWrapper, MAX_NODE>::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<NickName> 的方式存储十颗线段树。

  10. 为什么我用 make_STTable<int>(10, std::min<int>) 创建一个最小值表没问题，用 make_STTable<int>(10, std::max<int>) 创建一个最大值表没问题，但是我同时把两句代码写出来，表就出错了？

    本模板库的容器，以类型作为两种容器的区别特征；而 std::min<int> 和 std::max<int> 的类型相同，所以会把两个容器视为同一种容器。换句话说，后一个容器传入的函数指针会把前一个容器的函数指针覆盖掉，导致功能紊乱。

    一般而言，本模板库不推荐使用函数指针作为操作符的容器；使用匿名函数作为操作符的容器，运行效率更高，也减少了出错的概率。

About

C++ template files for competitive programming

Resources

Readme
Activity

Stars

160 stars

Watchers

2 watching

Forks

31 forks
Report repository

Releases

No releases published

Packages

No packages published

Languages