使用约定与迁移¶
源码、头文件路径和网页分类采用同一套目录：
| 目录 | 内容 |
|---|---|
noya/head.hpp |
高频使用的公共入口，保留简短 include |
noya/ds/ |
数据结构 |
noya/graph/ |
图与树算法 |
noya/string/ |
字符串 |
noya/math/ |
数论、代数、多项式 |
noya/geometry/ |
计算几何 |
noya/dp/ |
动态规划 |
noya/optimization/ |
优化与搜索 |
noya/utility/ |
调试、I/O、随机工具 |
写题仍可用 #include "noya/head.hpp"；具体模板例如
#include "noya/ds/sparse_table.hpp"。除公共入口外，旧的平铺路径不再保留；
仓库内测试、验证程序和展开工具已同步迁移。网站从目录发现分类，新增头文件
仍需写明复杂度、前置条件、中文用途，并补充对应的验证用例。
写题与预编译¶
保留源码开头的 #include "noya/head.hpp"，方便普通编译和展开提交。
Linux/macOS 安装 Python 3 与 GCC/Clang 后，可以从题目目录直接编译：
bash ~/libra/compile.sh main.cpp -o main -- -O2
CXX=clang++ bash ~/libra/compile.sh main.cpp -o main -- -O2
# 可选：在同一工作目录提前构建同样选项的缓存
bash ~/libra/precompile.sh -- -O2
# 使用提交模式编译，关闭默认 local 调试宏
bash ~/libra/compile.sh main.cpp -o main --submission -- -O2
第一次自动构建 PCH，之后复用；编译器、选项、模式或依赖变化会选择新的缓存。
缓存位于库内 .cache/pch/，不会在源码旁生成 .gch。
默认选项来自 compile_flags.txt，额外编译选项放在 -- 后面；
配置文件的相对 include 路径基于库目录，命令行相对路径基于当前题目目录。
这个入口会在源码之前载入公共头。影响公共头的宏（例如 local、NDEBUG）
必须通过 -D/-U 设置，不要依赖源码中 include 前的宏定义。
--submission 是本地编译模式，单文件提交仍使用展开器。
普通编译命令不会自动使用这里的独立缓存；使用 compile.sh，或在自己的 CMake
目标上调用 target_precompile_headers。详细缓存说明见仓库 tools/README.md。
Monoid 与 build¶
build 是正常的重建入口，构造函数使用同一套实现。Monoid 统一提供
value_type、unit()、op(a, b)。op 必须满足结合律，unit() 是双侧单位元；
普通 sparse table 还要求幂等性。运算须保持从左到右的顺序，不要求交换律。
#include "noya/ds/sparse_table.hpp"
#include <algorithm>
#include <limits>
#include <vector>
struct minimum {
using value_type = int;
static int unit() { return std::numeric_limits<int>::max(); }
static int op(int a, int b) { return std::min(a, b); }
};
int main() {
std::vector<int> values{5, 2, 7, 1};
noya::sparse_table<minimum> table(values);
int x = table.prod(1, 4); // [1,4)，得到 1
table.build(std::vector<int>{8, 3});
int y = table.get(0); // 8
table.build(4, [](int i) { return i * i; });
return x + y == 9 ? 0 : 1;
}
sparse_table、disjoint_sparse_table、segtree、lazy_segtree 共用数组构造、
build(values)、build(n, generator)、get(i)、prod(l,r)、all_prod()、
size()、empty() 约定。默认构造为空；空区间返回 unit()。
lazy_segtree<Monoid, Action> 的 Action 仍需提供映射及复合操作。
| 场景 | 类型 | 构建 | 区间查询 | 更新 |
|---|---|---|---|---|
| 静态幂等运算，如 min/max/gcd | sparse_table<Monoid> |
O(n log n) | O(1) | 重建 |
| 静态一般结合运算 | disjoint_sparse_table<Monoid> |
O(n log n) | O(1) | 重建 |
| 单点修改 | segtree<Monoid> |
O(n) | O(log n) | O(log n) |
| 区间映射 | lazy_segtree<Monoid, Action> |
O(n) | O(log n) | O(log n) |
| 队尾加入、队首删除 | swag<Monoid> |
O(n) | 整队 O(1) | 均摊 O(1) |
复杂度按值类型和 op/映射为 O(1) 计；例如字符串拼接的实际代价取决于字符串长度。
SWAG 使用 push_back、pop_front、all_prod，也支持数组构造、build 和 clear。
旧的 sparse_table<Value, op, identity> 与 swag<Value, op, identity_function>
改为 Monoid 类型接口。
容器拥有自己的值，不保存调用者数组的引用。静态表可用
table.build(std::move(values)) 接管原数组存储，调用后不要依赖原数组内容。
线段树的生成器版本直接填充叶子，不构造中间数组。静态表重建复用各层容量并按下标写入；
不使用 clear 破坏内层缓冲区，也不把 reserve + push_back 当成通用优化。
Monoid 和树查询均在编译期分派，没有虚函数或 std::function 调用。
树接口分层¶
根深度统一为 0，根父亲为 -1，子树区间为 [l,r)。
| 需求 | 类型 | 构建 | 查询 | 存储 |
|---|---|---|---|---|
| 父亲、深度、DFS 序、子树区间 | tree_preprocessing |
O(n) | O(1) | 五个线性数组 |
| 高频 LCA 与距离 | fastlca |
O(n log n) | O(1) | 基础数组与单整数 RMQ 表 |
| 路径拆分、向上跳、路径第 k 点 | hld |
O(n) | O(log n) | 基础数组、重儿子和链顶 |
三者共用迭代遍历；HLD 不保留邻接表副本，RMQ LCA 不建立额外倍增表。
通用的祖先判断、换根 LCA、路径相交等由编译期分派共用。
build_virtual_tree(tree, vertices) 接受任一查询实现的 const 引用，
复杂度为 O(k log k + k × LCA 查询耗时)，不会复制底层树。
fastlca(graph, root) 根据边类型识别无权/整数权树，不再接收权重开关。
有权根距离和查询结果须能用 int64_t 表示。
fastlca 原来的 kth_ancestor、kth_on_path 改用 HLD；
HLD 原来的 get_kth_ancestor、get_kth_node_on_path 统一为
kth_ancestor、kth_on_path。重建为空树会清除旧状态。
几何覆盖¶
原有模块包括二维基本谓词、凸包、半平面交、最近/最远点对、最小覆盖圆、圆交点与切线、 Minkowski 和、矩形面积并、凸层、三角形计数和欧氏最小生成树。 补充的常用接口如下：
| 头文件 | 接口与复杂度 |
|---|---|
geometry_distance.hpp |
投影、对称点、点到直线/线段、线段间距离，O(1) |
convex_polygon.hpp |
O(n) 规范化，O(log n) 点定位；O(n) 裁剪和重心 |
circle_polygon_area.hpp |
两圆交面积 O(1)，圆与多边形交面积 O(n) |
geometry_3d.hpp |
三维向量、混合积、点线面距离、平面投影、线面交、四面体体积，O(1) |
点定位沿用 -1 外部、0 边界、1 内部。直线和三维平面的退化结果使用
std::optional；零长线段按点处理；零面积多边形没有面积重心。
原有 point<T> 的整数点积、叉积及方向判断在 T 内计算，调用者须保证中间结果不溢出，
必要时用 point<__int128>。浮点距离和面积接口使用 long double；容差含义及输入
前置条件以各函数注释为准，并非任意量级下的精确几何。
仍可按题目需求补充的方向是三维凸包、多边形布尔运算、圆面积并，以及独立的 Delaunay/Voronoi 接口。这些没有以未验证的占位实现加入本库。
展开器¶
Python/Sublime 与 VS Code 实现使用同一组语义测试：
- 支持单行字面量 quoted include、子目录、相对依赖和
#pragma once。 - 提交输出删除头文件宏守卫和
#pragma once，并对受保护的重复依赖去重。 - 保留
#if defined(local)等功能条件；跨条件分支的重复依赖按实际包含条件处理，不生成头文件守卫。 - 系统 include 保持原位置；条件分支、宏开关、重复无守卫包含和
#undef后重包含交给编译器处理。 - 有守卫的循环依赖可展开；活动的无守卫循环产生编译错误，避免无限递归。
宏生成的 include 和系统头不进行本地展开。Python 配置中的相对库路径按配置文件目录解析， 不依赖当前终端目录。VS Code 多选复制按文档换行风格连接。 上面的多选行为仅用于显式展开命令；普通 Cmd/Ctrl+C 与 Sublime 适配层一致， 仅展开单个非空 C++ 选区中的真实库 include。空选区、多选、普通文本、注释和字符串 使用原生复制；展开保留选区空行、换行风格和末尾换行。 若控制重复包含的条件宏中途变化，且清理守卫需要其旧值，展开会报错，普通复制回退为原生复制。