Reaepita's Blog

给定二维平面上的点集，凸包就是将最外层的点连接起来构成凸多边形，它能包含点集中所有的点。 构造方法若 则 在 的顺时针方向 若 则 与 共线 若 则 在 的逆时针方向 ①极角排序选择一个点作为基础点，进行极角排序。 可以通过比较叉...

定义：半平面： 顾名思义，就是平面的一半。一条直线会把平面分成两部分，就是两个半平面。对于半平面，我们可以用直线方程式如： 表示，更常用的是用直线表示。 半平面交： 顾名思义，就是多个半平面求交集。其结果可能是一个凸多边形、无穷平面、直线、线段、点...

单调队列&单调栈斜率优化四边形不等式带权二分决策单调性

有向图游戏与 SG 函数常见类 nim 游戏

多项式与生成函数代数基本定理拉格朗日插值常用算法FFTNTTFWTk 进制 FWT分治FFT多项式乘法逆多项式求导/积分多项式牛顿迭代多项式开根多项式快速幂多项式对数函数多项式指数函数多项式多点求值多项式快速插值普通生成函数指数生成函数排列组合常见组...

树相关树的直径树上LCA欧拉序树的重心树上启发式合并树链剖分长链剖分重链剖分虚树矩阵树定理最小生成树最短路差分约束强连通分量割点/桥2-SAT网络流最大流最小割费用流Prufer 序列支配树

前缀相关KMPZ 函数AC自动机Trie后缀相关后缀数组后缀自动机后缀平衡树广义后缀自动机回文相关Manacher回文树Lyndon 分解最小表示法

并查集路径压缩按秩合并块状数据结构分块莫队树上莫队带修莫队平衡树李超线段树动态树树套树K-D Tree

数论算法快速乘12345ll mul(ll a,ll b,ll mod){ ll tmp=a*b-(ll)((long double)a/mod*b+0.5)*mod; return tmp<0?tmp+mod:tmp;} 同余系相关Exgc...