Library 聚合一

aaron0919 · 2025-11-20 21:35:15 · 个人记录

Library 聚合一

所有代码皆来自于 https://judge.yosupo.jp/，旨在促进编程竞赛通用库的发展。

以下列出个人认为比较有用的库，只提供链接，不造成侵权，欢迎大佬认领代码。

缺点是大部分都要改改才能兼容 C++14，但是我只能分享，所以理性喷。

只收录了比较清新的板子好多脱俗但不清新的，可以直接用（C++20）。

建议科学上网，欢迎补充。

:::warning[注意]{open} 你要在茫茫快读板子中（以及神秘模板）找到算法是一件很难的事，需仔细辨认。

所以说后面就开摆了，但选的都应该比较好。

这不给个赞。 :::

测试

IO

• 33ms，兼容 iostream by hiro1729
• 34ms，可以 read(a,b) by drken
• 34ms，兼容 iostream by 作者未知

个人喜欢第三个，嘻嘻，就是我改的，C++14 也能用。

数据结构

只选了常用的。

哈希表

• 44ms，封装两类 by mayaming
• 52ms，封装了字符串 by oldyan

有序数组

• 86ms，块状链表 by nandhagk
• 87ms，树状数组 by cmk666
• 87ms，封装齐全 by oldyan

ST 表

• 见 LCA&RMQ，这题写的都很脱俗。

并查集

• 5ms，by (Anonymous)

线段树 2

• 273ms，封装 zkw by oldyan
• 280ms，封装类似 ac-library by tonegawa

区间 kth

• 71ms，没有封装 by (Anonymous)
• 79ms，清新些 by Zhao Yuyang
• 87ms，封装小波树 by TumoiYorozu

区间众数

这种分块都没什么高扩展性，就随便选了个。

• 77ms，封装了个寂寞 by oldyan
• 84ms，无封装 by robinyqc

二维数点

找不到分块套数做法，应该很快啊。

• 111ms，cdq by oldyan
• 264ms，小清新做法 by denverjin
• kdt 乱入，我写的

加点二维数点

• 151ms，封装过火 by oldyan
• 180ms，小波树套树状数组？by maspy
• kdt 乱入，我写的

扫描线

• 435ms，线段树 by tonegawa

图论

不擅长，乱选的。

最短路

• 62ms，STL 堆优化 by Yuezheng_Ling_fans
• 68ms，同上但空间小 by h_squared

SCC

• 51ms，最快 by Kiffaz11
• 77ms，封装 by oldyan
• 117ms，清新 by vjudge1 Jerrywang

你说 vjudge1 算不算匿名用户。

EBCC

• 26ms，最快 by Kiffaz11
• 27ms，封装 by oldyan
• 48ms，清新有注释 by vjudge1

(V)BCC

• 68ms，最快 by Kiffaz11
• 100ms，封装 by oldyan
• 144ms，清新有注释 by vjudge1

欧拉路径（无向图）

• 68ms，最快 by Kiffaz11
• 100ms，封装 by oldyan

二分图最大匹配

• 121ms，最快 by anon123
• 155ms，封装了吧 by (Anonymous)

一般图最大匹配

• 1ms，最快 by nor

最小生成树

• 40ms，kruskal 清新 by Kiffaz11

欧拉回路计数

• 26ms，最快 by adamant

矩阵树

• 100ms，胜在清新 by robinyqc

树论

树直径

都是神秘 dp，注意不是树形 dp，放一个。

• 29ms，最快 by nullchilly

LCA&RMQ

都是欧拉序。

• 24ms，最快 by chaihf
• 37ms，有 RMQ 封装 by nullchilly

求和

我放弃了，只给最清新的，名字是乱翻的。

准确地说是看最优解前十名写的最短的，等价于乱选。

单点加路径求和

• 116ms，神秘多叉线段树 by mukundan314

顶点集合路径组合

不会翻，真的不知道题目名想干什么。

• 226ms，清新 by ivgechu

单点加子树求和

• 35ms，还是多叉树线段树 by mukundan314

单点加（范围）邻域求和

• 361ms，比较清新 by CYMario

（范围）邻域加单点求和

• 289ms，比较清新 by ahsoltan

定根点集树路径组合和

• 340ms，比较清新 by Warinchai_s

点集树路径组合和

• 330ms，站长的 by yosupo

LCT

怎么还有动态版啊。

动态树单点加路径求和

• 83ms，最快 by chaihf

动态树顶点设置路径组合

• 110ms，最快 by chaihf

动态树单点加子树求和

• 127ms，最快 by chaihf

动态树子树加子树求和

• 156ms，最快 by chaihf

笛卡尔树

• 28ms，封装 by cmk666

卷积

// TODO