-
总起
现在是 2026 年 7 月 24 日，我正在整理并打算公开一部分我的 OI 笔记。 一开始我打算学 command_block 那样搞一个目录之类的，后来我发现，cmd 还是太小而美了，我记笔记的习惯已经积累了较为恐怖的笔记量。 目前只整理了一部分... -
tricks
对一个凸包和一个普通数组做卷积 根据决策单调性的知识，我们需要根据卷积和凸包的方向是否相同，来利用四边形不等式（分治）或反四边形不等式（二分栈）来优化该过程，时间复杂度 O(nlogn)\mathcal O(n\log n)O(nlogn)。 gc... -
随机化_LCA
P10850 [EGOI2024] Light Bulbs / 灯泡安装 P10698 [SNCPC2024] 最大流 CF1641D Two Arrays CF364D Ghd CF1305F Kuroni and the Punishment -
阶_LCA
阶 一天，小灰在学习阶的求法时，在代码里写下了这样一句： 1assert((a^b)%p==a%p); 调出来的小灰气急败坏，于是让你解决这个问题：qqq 组询问 a,pa,pa,p，求最小的正整数 bbb 使得 (a⊕b)≡a(modp)(a\o... -
dp优化——lca_专题_LCA
dp 优化——lca [AGC017F] Zigzag 给定一个 NNN 层的三角形图，第 iii 层有 iii 个节点。 第 iii 层的节点，从左到右依次标号为 (i,1),(i,2),…,(i,i)(i, 1), (i, 2), \ldots... -
地狱数位dp：圆滚滚的算术占卜_根
地狱数位 dp：圆滚滚的算术占卜 #3641. 「2021 集训队互测」圆滚滚的算术占卜 在具有高度智慧的、拥有“史莱姆的导师”之称的红头史莱姆的引导下，史莱姆们理解了十进制数，并能够利用数字进行占卜。 史莱姆每天会进行占卜活动，第 kkk 天的流... -
dp方法——状态机的判定_专题_LCA
dp 方法——状态机的判定 随笔。 大多数 dp\rm dpdp 都是套了一个判定方法当状态。 序列 dp\rm dpdp 考虑从左往右判定的过程。 局限性：总是状态机的第 iii 个时刻转移到第 i+1i+1i+1 个时刻，无法跨层转移。 所以不管... -
二分图边染色摘抄&KM复习_专题_LCA
xlpg0713 二分图边染色 摘抄 原文。 二分图边染色 板子：[CF600F] Edge coloring of bipartite graph 给定一张二分图，你需要把边染色，使得颜色数尽量少。 复杂度 nmnmnm。 首先可以证明答案是 ... -
分块套分治_专题_LCA
分块套分治 P5611 [Ynoi2013] D2T2 给一个长为 nnn 的序列，有 mmm 次查询操作。 查询操作形如 l r L Rl\;r\;L\;RlrLR，表示将序列中值在 [L,R][L,R][L,R] 内的位置保留不变，其他的... -
树上信息统计_专题_LCA
树上信息统计 绝大多数时候，我们会统计树上联通信息，例如子树信息、链信息、邻域信息。 联通信息有时可以点边容斥。 虚树、子树、链、普通连通块通常在 lca\rm lcalca 处统计，邻域通常在中心处合并。 O(1) 链 max 对树建极值分治树，等... -
树上信息表示（欧拉序括号序prufer）_专题_LCA
树上信息表示 欧拉序 树的一条欧拉回路上的点的序列。 欧拉序上的区间 mindep\rm mindepmindep 是 lca\rm lcalca，从浅往深走加左括号，从深往浅走加右括号，那么区间括号匹配后剩下的部分就是这条路径的信息。 后者被称为括... -
LCA组合方法_专题_LCA
LCA 组合方法 组合问题的形式：通常有一个个体集合 UUU，以及形式方案集合 VVV，其每个元素都是个体集合的子集：∀v∈V,v⊆U\forall v\in V,v\sube U∀v∈V,v⊆U。 每种方案都有一个权值，在判定问题中是 0/10/1... -
LXLDStricks_专题_LCA
LXL DS tricks 单侧递归系列 区间函数复合 每个节点是一个函数，区间询问给定值通过 l,⋯ ,rl,\cdots,rl,⋯,r 这些函数值变成什么。 两种思路，直接维护和标记回收，都是没有修改的情况。 直接维护就是维护一棵线段树，每... -
LCA图论_专题_LCA
LCA 图论 点/边覆盖 点/边独立集 我们常说的匹配就是边独立集。 在一般图上点覆盖 ≥\ge≥ 边独立集，边覆盖 $\ge $ 点独立集，这是因为一个点/边不可能覆盖独立集里的多个边/点，二分图上二者可以取等。 注意边覆盖的定义需要图中无孤点，否... -
LCA智慧构造_专题_LCA
LCA 智慧构造 CF1762D GCD Queries 这是一道交互题，ttt 组数据。 有一个 0∼n−10\sim n-10∼n−1 的排列 ppp。你可以进行以下询问最多 2n2n2n 次： ? i j：询问 pip_ipi 和 pjp... -
LXLtreetricks_专题_LCA
LXL tree tricks CF1260F Colored Tree 给定一棵树，每个节点有一个颜色hhh，hih_ihi为[Li,Ri][L_i,R_i][Li,Ri]内的一个整数。 现在，对于所有∏(Ri−Li+1)\prod (R_... -
LXL根号数据结构_专题_LCA
LXL 根号数据结构 区间逆序对 常用的做法是莫队 + 树状数组，还有二离莫队，还有分块。 其实我们可以用扫描线的角度考虑，我们对每个点维护右下角被点亮的点数，查询一条线右边的点权和，右端点右移时矩形加。 KDT 即可单根号。 莫队 莫队可以解决两个... -
YunQianDStricks_专题_LCA
YunQian DS tricks 另类线段树分治 与朴素的插入删除线段树分治不同，如果我们很容易解决先修改后询问（即可能要对修改做某种整体处理），并且询问的形式可以拆开贡献（例如 sum max...\text{sum max...}sum max... -
叶子川Mathtricks_专题_LCA
叶子川 Math tricks 容斥原理 容斥的暴力方法是寻找条件，然后钦定这些条件不成立。 容斥的证明方法： ∑∏p=∑∏(1−q)=∑(−1)∣S∣∏i∈Sqi\sum\prod p=\sum\prod(1-q)=\sum(-1)^{|S|}\p... -
KM复习_LCA
KM 复习 附：HK 算法求二分图最大匹配 在求二分图最大匹配时，常数更小空间也更小的写法是使用 HK 算法。 其实就是只用了流的有效部分，去除了臃肿的部分。 每次只找最少边数的增广路集合，能多找就多找，至多 n\sqrt nn 轮（不会证）。 流... -
反悔贪心（模拟费用流）_LCA
反悔贪心（模拟费用流） 模拟费用流的重点是维护流一步、以及维护负环。 只要能维护这两个，就无需维护退流，并且进行任意形式的修改（即给定一个残量网络）都能保证正确性。 思考的时候最好先从最优化形式想到费用流，再从费用流模型系统地思考这两个问题，以及如果... -
复杂度鉴赏_LCA
复杂度鉴赏 诸如 2n2^{\sqrt n}2n 之类的奇怪复杂度，这种题目可能有两种情况： 某些自然成立的不等式，导致实际需要枚举的量并不多，除法或开根出现在指数上带来极大的复杂度优化。 两种不同复杂度的算法皆能解决这个问题，平衡后得到一个奇怪... -
无向图子图计数-摘抄_LCA
P1989 无向图三元环计数 小度连大度（或者大度连小度），复杂度 mmm\sqrt mmm，分讨易证。 四元环计数 考虑对点按度数排序，枚举最后面的点 aaa，枚举它的对面点 ccc，那么满足 a→b,(b,c)a\to b,(b,c)a→b,(... -
模拟费用流_LCA
模拟费用流 重要性质 模拟费用流的流量通常表现为选点的个数，在构造时要对着这个构造。 在图不变的情况下： 增广一次（多 111 的流量），与源汇相连的边不会发生退流。 增广一次，增广路不会经过一个点两次，否则意味着上次的结果中有负环。 若我们（通... -
网络流 - 模型_LCA
网络流 经典模型 二分图最大匹配/最大权匹配 最大权匹配等价于拆点后的最大匹配，S→axx→∞y→ayTS\xrightarrow{a_x} x\xrightarrow{\infty} y\xrightarrow{a_y} TSaxx∞yay... -
网络流 - 技巧_LCA
网络流 - 技巧 最大流 设定一个源点，一个汇点，只有这两个点可以流量不平衡，则 SSS 向外最大的流量就是该定义下的最大流。 使用 Dinic 算法解决，比较快的实现方式可以看下文“更快的 Dinic”。 费用流 每条边 iii 自带一个费用，表示... -
证明_LCA
证明 排序问题 值域压缩原理 常见的值域压缩是离散化，但更加强力的值域压缩是枚举中值，然后把序列变成 0/1/−10/1/-10/1/−1。 0/10/10/1 序列逆序对数，相当于 000 看成向右走，111 看成向上走，那么逆序对数相当于折线右... -
Steiner系初探_退役期间
Steiner 系初探 我好久没有写学术文章了，因为对比起大家在研究的内容，文化课上的内容实在是缺乏美感与研究价值。 废话少叙，让我们来看一些有意思的东西。 引入：沪卷一模 12 题。 设平行四边形 A1A2A3A4A_1A_2A_3A_4A1A... -
一类dp优化——统计答案优化_杂项
一类dp优化——统计答案优化 这个名字可能挺抽象的，没想到什么好名字。 这类 dpdpdp 的特征是：有一维状态不参与转移的系数，只是转移的时候改变本身的位置，这维状态仅用来统计答案而设立。 例如经典分段形式的 dpdpdp，求方案数我们都会朴素的 ... -
谈一类特殊回滚莫队——链表莫队_杂项
谈一类特殊回滚莫队——链表莫队 灵感源自这篇题解，看了很久才看懂，纪念一下。 取这个名字是因为它既不像只增不删也不像只删不增，但其可以维护一类较为有普遍性的问题——区间相邻值最值问题。 例如区间查询值域上连续三个数的差的平方和的最小值，或者求任何关于... -
Ad-Hoc_杂项
Ad-Hoc 其实就是纯种思维题。 来锻炼一下吧。 P8866 [NOIP2022] 喵了个喵 相信大家都知道题意。 k=2n−1,n≤300,∑m≤106,T≤1005k=2n-1,n\le 300,\sum m\le 10^6,T\le 100... -
Exchange Arguments_杂项
Exchange Arguments 若相邻两项交换对总权值的影响无需用到两项之外的元素，则我们可以使用相邻交换贪心来处理这类问题。 在实际处理的时候若比较可以写为 x<y ⟺ val(x)<val(y)x<y\iff val(... -
NFLS 博弈杂记_杂项
NFLS 博弈杂记 Nim 游戏 nnn 堆石子，每次选一堆拿走正整数个，无法操作者输。 结论是 ⨁iai=0\bigoplus_{i} a_i=0⨁iai=0 则先手必败否则先手必胜，⊕\oplus⊕ 表示按位异或。 证明：若 ⨁iai=0\b... -
传递性_杂项
T3 一棵树，从一号点出发，点有点权，边有边权，经过一条边会将血量扣除这条边的边权，首次到达一个点血量增加这个点的点权。 任何时刻血量不能为负，问从 111 出发回到 111 至少要多少初始血量。 n≤105n\le 10^5n≤105。 这个题... -
数位 dp 进阶（数位自动机）_杂项
数位 dp 进阶（数位自动机） 通常来说，我们遇到的数位 dp 都是在原状态上加上 d,z,cd,z,cd,z,c 表示第 ddd 位，是否顶格，本位选择的数。 也可以枚举计算数字与上界的 lcplcplcp，然后处理后面任意选的方案。 数位 dp\... -
期望 dp 的转移_杂项
期望 dp 的转移 我们通常会对一个过程进行期望 dp，此时就必定会涉及到期望的定义问题： 到达每个状态的概率本就有别，只有初状态和终状态的概率是 111，那此时对状态的“期望”如何定义？ 按正常的理解思路，期望中蕴含着概率，是概率的积分，自然概... -
轮廓线 dp_杂项
轮廓线 dp 也叫插头 dp\text{dp}dp，大部分时间叫插头 dp\text{dp}dp 多一些，毕竟字少。 给定一个二维平面，让你填数，如果我们一次要用到一行信息，那我们枚举本行和下行状态就要达到 Θ(4min(n,m)max(n,m)... -
Boruvka & Kosaraju_杂项
Boruvka & Kosaraju 它们都是图论中的冷门算法，且能用来解决一部分困难的问题。 Kosaraju 先说这个，这个比较简单。 简单来说就是两遍 dfs 即可求出强连通分量，利用了后序 dfn 的某些性质。 流程： dfs 一遍... -
DAG上容斥_杂项
DAG上容斥 如果你是先看题解再做题，自然地接受了这一套路的话，那你很难想象这为什么是黑题。 [ABC306Ex] Balance Scale 给定一个无向图，你需要把每条边定为 >,<,=>,<,=>,<,= ... -
FastDivFastMod_杂项
FastDiv/FastMod 假： 原理： 1inv[i]=-1ull/i+1,a/b==(i128)a*inv[b]>>64,a%b==a-a/b*b 所以在输入模数的情况下可以加速取模。 12345678struct FastMod... -
AC自动机_杂项
8.2 专题：AC自动机 今日警钟：a[read()][read()]会死。 好好好。 一年前就 AC 了三道 ACAM 板子，然后全忘了。 本来寻思着重拾，但又不知道摆到哪里去了。 还好南外帮我重拾了哈哈哈哈哈。 发现这里效率真的高，一天差不多就学... -
SG函数_杂项
SG 函数 属于博弈论的一种构造吧。 就有些东西你第一次接触就会感觉很莫名其妙，看了证明后觉得是不是还存在第二种解，直到对它的理解逐渐深入。 P2197 【模板】Nim 游戏 nnn 堆石子，第 iii 堆有 aia_iai 个，每个人每次可以选... -
众数杀手_杂项
众数杀手 感觉坑越开越多了。 最好的写法就是 set 找前驱后继。 rsrams 已收录于“lxl 根号数据结构”。 CF1446D1 给定序列 aaa，求最长的满足区间众数有至少两种的区间长度。 n≤2×105,ai≤100n\le 2\time... -
分块维护不带修区间点对信息_杂项
分块维护不带修区间点对信息 通常求的是 ∑i=lr∑j=lrf(i,j)\sum_{i=l}^r\sum_{j=l}^r f(i,j)∑i=lr∑j=lrf(i,j)。 由于贡献可差分，我们可以利用分块按照一定套路求。 维护如下信息： pxp_... -
单源正权单调求和最短路通用解法_杂项
正权单调求和最短路通用解法 对于所有最短路定义为 d(e1,e2,e3,… )=∑iw(ei,ei+1)d(e_1,e_2,e_3,\dots)=\sum_iw(e_i,e_{i+1})d(e1,e2,e3,…)=∑iw(ei,ei+1)... -
同余最短路_杂项
同余最短路 不整东西还是遗忘的快啊…… 同余最短路大概是鼓励你把 dp\text{dp}dp 的某一维改成同余意义下，然后通常转移就成环了，然后你就顺理成章的用最短路来解决。 首先这得是个最优化问题。 来看几个套路吧： 超大容量背包 P2371 [国... -
如何把五方优化到线性？_杂项
如何把五方优化到线性？ 一个长度为 nnn 的排列的权值定义为：∑irsi−lsi\sum_irs_i-ls_i∑irsi−lsi，其中 ls,rsls,rsls,rs 是笛卡尔树（大根堆）上左右儿子。 求出所有长度为 nnn 的排列的权值。... -
整体二分_杂项
整体二分 不详细说概念了，大概就是放在一起二分，从而压缩掉一些操作。 常见的写法就是 void sol(L,R,vec) 表示 vec 里面的点二分到 L,R。 当然如果具有某种决策单调性我们可以把 vec 换成 l,r。 大多数时候需要撤销，即判断... -
数点问题_杂项
数点问题 开坑，数点基础太弱了，总是被坐标转换折磨的痛不欲生。 来一些自己总结的减轻痛苦的技巧吧。 用演算纸，这个肯定是基础，如果你的大脑不是 64 位的，不要自信到纸也不拿。 多换元，一些线性的坐标变换直接用新元代替，不要保留一坨加一减一加常数之... -
欧拉降幂_杂项
欧拉降幂 扩展欧拉定理： ab≡{ab mod φ(m),a⊥mab,a⊥̸m,b<φ(m)ab mod φ(m)+φ(m),a⊥̸m,b≥φ(m)(modm)a^b\equiv\left\{\begin{aligned}&a^{b\b... -
正交线性基_杂项
正交线性基 看了一晚上Sooke’s 正交线性基的介绍，现在已经变成线性代数人了。 格物致知。 Z2n\mathbb Z_2^nZ2n 表示 nnn 维，每维 mod 2\bmod \ 2mod 2 的空间，我们称这其中选出的一组线性无关的向... -
组合计数_杂项
组合计数 收录一些题吧。 理论 定义式及基本性质： (nm)=n!m!(n−m)!,(nm)=(nn−m),(nm)=(n−1m)+(n−1m−1)\binom{n}{m}=\frac{n!}{m!(n-m)!},\binom{n}{m}=\bino... -
鞅_杂项
鞅 直观来讲，鞅是满足下述条件的随机过程：已知过去的某个时刻 sss 及之前的所有观测值，对于以后的任意时刻 ttt，ttt 的观测值的条件期望等 于 sss 的观测值。 形式化的定理考虑了很多边界情况，通常来说，使用鞅只需要构造势函数 ϕ\phiϕ... -
树上高消_随笔
树上高消 高斯消元我们都知道，是难以优化的三方算法，我们在这里限定高斯消元解决的是线性方程组问题。 引入——树上随机游走 顾名思义，给定每个点到每个邻居的系数，有一些点是终止态，到达后不能再游走，求每个节点期望经过次数（这个次数对于终止态来说就是到达... -
线性数据结构 2：根路径度数_随笔
线性数据结构 2：根路径度数 问题形式：给定一棵树，qqq 次询问 x,kx,kx,k 表示求 xxx 到根路径上第 kkk 小的度数，可离线。 弱化版：求 kkk 这个度数的 rank\rm rankrank，即询问有多少个 ≤\le≤ 它的。 度... -
线性数据结构初探：加删查最小众数_随笔
线性数据结构初探：加删查最小众数 问题形式：有一个集合，你可以向其中加入一个数、删除一个数、查询出现次数最多的数中最小的那个。 值域和询问次数是线性，修改次数 nnn\sqrt nnn，要求空间线性，最好能禁止哈希表。 注意：不保证任意时刻集合大小... -
DAG 链剖分_随笔
DAG 链剖分 一句话，令 fxf_xfx 是到达 xxx 的路径数量，gxg_xgx 是从 xxx 出发的路径数量，则 (u,v)(u,v)(u,v) 是重边当且仅当 uuu 是 vvv 中的 maxf\max fmaxf，vvv 是 uuu... -
NTT 入门_随笔
NTT 入门 牢记目标：对于一个给定的 m−1m-1m−1 次的多项式（m=2nm=2^nm=2n），我们要求出 mmm 个点 ωmk\omega_{m}^{k}ωmk 代进去的点值，有了点值我们可以进行多项式乘法等内容。 把多项式奇偶分类，F(x... -
exLucas 平替_随笔
exLucas 平替 我们知道，exLucas 是 O(min(n,p))\mathcal O(\min(n,p))O(min(n,p)) 的，所以 ppp 很小时，nnn 可以开到 101810^{18}1018。 不过很多时候，只是模数为合数而... -
max、逻辑与绝对值_随笔
max、逻辑与绝对值 在诸多时候（例如组合计数），我们很方便处理加与乘，此时 max\maxmax 这种东西对我们是一个头疼的东西。 同样令我们头疼的还有逻辑与、逻辑或、绝对值，这些东西在一定前提下是可以互相转化的，显然将所有形式转化到一起，有利于... -
WBLT_随笔
WBLT Treap\rm TreapTreap 足够优秀，但其缺憾有几点： 并不 Leafy\rm LeafyLeafy，合并需要合并三份而不是两份，在上面进行线段树操作更加繁琐，查询区间信息需要裂开合并，不能直接像线段树一样求。 如果对其进行可... -
信息合并：where 结合律 from？_随笔
信息合并：where 结合律 from？ 在构造历史和相关问题的信息合并时，我们通常会发现已构造信息的合并不够封闭，所以我们增加新的信息直到它封闭。 而对于另一类问题，我们有可能会发现：信息是可以合并的，但是这玩意没有结合律，我们就无法用已有的强大数... -
后缀树的 dfn 是字典序_随笔
后缀树的 dfn 是字典序 这个东西十分的深刻，因为有一天我回看 TJOI 弦论代码的时候，我发现后缀树上每个节点明明代表了一类 endpos\rm endposendpos 集合相同的串，但我们在自动机上跑的时候却没事！ 关心自动机结构的时候就不要... -
打表：威佐夫博弈与 k 倍动态减法_随笔
打表：威佐夫博弈与 k 倍动态减法 威佐夫博弈 两堆石子，每次可以取 (x,y)(x,y)(x,y)，你需要保证 x+y≥1x+y\ge 1x+y≥1 并且 x:y=(1:1)/(1:0)/(0:1)x:y=(1:1)/(1:0)/(0:1)x:y=... -
归约小记_随笔
归约小记 问题和计算能力 问题 我们定义为 010101 串到 010101 串的映射，在多项式意义下，可以定义为 010101 串到 0/10/10/1 的映射，即所有问题都是判定问题。 后者也被称为语言，一个语言可以用一个集合 SSS 表示，里面... -
数学小记：1988IMOP6_随笔
数学小记：1988IMOP6 改编版 OI 题：给定 nnn，对满足 (xy+1)∣(x2+y2),x,y∈[1,n](xy+1)\mid(x^2+y^2),x,y\in[1,n](xy+1)∣(x2+y2),x,y∈[1,n] 的 (x,y)(x,... -
excrtexgcd_算法
1234567891011void exgcd(ll a,ll b,ll &x,ll &y) { if(!b) return x=1,y=0,void(); exgcd(b,a%b,x,y);tie(x,y)=m... -
博弈模型_算法
博弈模型 Nim/SG 单开了一篇。 二分图博弈/无向图地理游戏 给定图，图上有一枚棋子，二人轮流沿边行动，走过的边不能再走，无法行动者输。 当且仅当棋子在所有最大匹配上时，先手必胜。 正确性比较显然。 二分图的情况当且仅当 SSS 到 vvv ... -
双射法_算法
双射法 还是有点震撼的。 教程关： 对于正整数 nnn，我们称⼀个正整数列 a[1,k]a_{[1,k]}a[1,k] 是 nnn 的有序划分，当且仅当 ∑ai=n\sum a_i=n∑ai=n。 给定 n≥2n\ge 2n≥2，求满⾜ ∑i=... -
离散对数阶原根剩余_算法
离散对数/阶/原根/剩余/数论科技 都是离散同余的内容。 离散对数 若 a⊥pa\perp pa⊥p，且 ax≡b(modp)a^x\equiv b\pmod pax≡b(modp)，则 xxx 称作离散对数 logab\log_ablogab。... -
虚树学习笔记_算法
虚树 前情提要：本文中括号较多，有的括号表示补充说明，有的括号将定语分层方便阅读理解。 首先列一个树上问题解决表（并不是很全）。 多想想dfs栈和dfs作差。 询问 解决思路 整棵树的问题 自底向上树上贪心/树形DP 链上问题 树链... -
DFA 最小化_算法
这里是好写的高复杂度写法，外层枚举字符不断分裂节点，mrk 是接受状态，to[u][v] 是颜色为 uuu 的点指向颜色为 vvv 的点会分配为什么颜色。 12345678910111213141516171819202122232425int co... -
K-D Tree_算法
K-D Tree 123456789101112131415161718192021222324252627282930//inner:d,outer:l,rusing ar=array<int,2>;using A=array<a... -
paring heap_算法
paring heap 1234567891011121314int mer(int x,int y) { if(!x||!y) return x|y; if(v[x]<v[y]) swap(x,y); r(y)=l... -
exkmp（Z 函数）_算法
exkmp（Z 函数） 代码很像 manacher，思路也很像。 作用是求一个串和每个后缀的 lcplcplcp。 1234567891011121314151617inline void Z(char *s, int n) { z[... -
tarjan_算法
更新：vector 存边板子 SCC： 123456789101112131415void d(int x) { dfn[x]=low[x]=++tot; s[++t]=x;in[x]=1; for(int v:G[x])... -
万能欧几里得学习笔记_算法
万能欧几里得学习笔记 万欧很好的点出了类欧的本质，告诉我们推那一串式子和推两个操作并没有任何区别。 目录： 万欧的概念、套路与代码实现 万欧解决的问题形式及例题 参考资料 万欧的概念、套路与代码实现 有一些概念性的东西： 定义 操作 为修改某个变... -
min-max 容斥_算法
min-max 容斥 式子： E[maxi=1nXi]=∑S⊆[n],∣S∣≥1(−1)∣S∣+1E[min{Xi}i∈S]E[\max_{i=1}^n X_i]=\sum_{S\sube[n],|S|\ge 1}(-1)^{|S|+1}E[\m... -
全局平衡二叉树_算法
全局平衡二叉树 可以较轻松的维护动态 dp\text{dp}dp，其他时候不建议使用。 其基础是静态的二叉搜索树，但并不是整个树结构都满足二叉，准确的说，每条重链使用一个二叉搜索树维护。 构建方式是对每条重链以轻子树大小和为权值按权分治找到左右儿子。... -
压位Trie_算法
压位Trie 能够 Θ(nlog64V)\Theta(n\log_{64}V)Θ(nlog64V) 进行插入删除求前驱后继。 其实就跟它的名字一样，只不过为了快使用了很多别样的写法。 由低位向高位存储，以下代码适用于 V<224V<2... -
对称压缩后缀自动机_算法
对称压缩后缀自动机 前言 后缀树，把所有后缀插到一个 Trie\rm TrieTrie 里，然后对其进行压缩，每个节点都表示了一个 left\rm leftleft 集合。 根据 DFA\rm DFADFA 最小化理论，接下来可匹配的后继相同，那么它... -
左偏树_算法
123456789101112131415int find(int x) {return x^f[x]?f[x]=find(f[x]):x;}int mer(int x,int y) { if(!x||!y) re... -
有限微积分_算法
有限微积分 不想延申太多，但提一下有限微积分的几个法则： 定义 Ef(x)=f(x+1),Δf(x)=Ef(x)−f(x),∑abf(x)δx=∑i=ab−1f(x)\mathrm Ef(x)=f(x+1),\Delta f(x)=\mathrm E... -
最小树形图_算法
最小树形图 之前没涉及到，这个贪心还挺牛的。 最小树形图定义在有向图上，即所有作为子图出现的叶向树的最小边权和。 解决最小树形图的算法是朱刘算法，暴力复杂度是 O(nm)\mathcal O(nm)O(nm)，tarjan 优化后可以做到 O(m+n... -
杜教筛Powerful Number_算法
杜教筛 推导过程 设现在要求积性函数 f(x)f(x)f(x) 的前缀和 S(x)S(x)S(x)。 用取整函数 [x][x][x] 表示下取整 ⌊x⌋\lfloor x\rfloor⌊x⌋，太懒了。 我们再构造一个函数 ggg（不需要积性），考虑 ... -
积性函数筛法（1）_算法
积性函数筛法（1） 本文来介绍一些基础性概念，为后文服务。 可能适合于已经会一点点下述内容的人来看，可能会增进你的理解。 积性函数 概念 Dirichlet\rm DirichletDirichlet 卷积 常见积性函数 线性筛 线性筛素数... -
积性函数筛法（后记）_算法
后记 本篇文章经过了多次重构，希望能达到一个我满意的效果。 对于积性函数筛法，我曾有相当大的心结在其中，这是一个学起来会相当破防的东西。 最初我只打算学一个杜教筛，然后我打开了洛谷模板最优解，我发现跑的最快的 @XeCtera 的 #10 跑了 18... -
积性函数筛法（2）_算法
积性函数前缀和筛法 起因是我正在学筛法，然后去看了一眼最快解。 没想到 P4213 【模板】杜教筛、P3768 简单的数学题、P5325 【模板】Min_25 筛 的最快解都被同一位大佬 @XeCtera 垄断，且前两篇的他还没有开 O2\rm O2... -
（需复习）二次离线莫队_算法
二次离线莫队 恶补知识点。 能 Θ(snn)→Θ(ns+nn)\Theta(sn\sqrt n)\to \Theta(ns+n\sqrt n)Θ(snn)→Θ(ns+nn)，其中 sss 是移动端点复杂度。 设 f(x,[l,r])f(x,[l,... -
颜色段均摊ODT_算法
颜色段均摊/ODT 由于时间原因，无法做大量的记叙，仅记录一些核心部分。 颜色段均摊指的是每次把一个序列的一个区间截出来（两端相交的段截断），把这个区间里所有的小段合成一个大段，总复杂度是 Θ((n+q)s)\Theta((n+q)s)Θ((n+q)... -
高斯消元_算法
高斯消元 朴素的实数高斯消元写的比较短的板子： 123456789void gauss(db a[C][C],int n) { F(i,1,n) { int ma=i; F(j,i,n) fabs... -
Lagrange插值_成型笔记
Lagrange\rm LagrangeLagrange 插值 补知识点。 多项式的点值表示法与系数表示法 这个应该很容易理解。 多项式的系数表示法就是 f(x)=∑i=0naixif(x)=\sum_{i= 0}^na_ix^if(x)=∑i=0n... -
从带权二分到闵可夫斯基和与凸生成函数_成型笔记
从带权二分到闵可夫斯基和与凸生成函数 写于 whk 时期，虽然开始 whk 之前就想写了，不过一直没时间。 不过 whk 这边让我学会了灵活的往时间轴里塞东西。 所以虽然我更忙了，但是我更有空了。 不说废话了。 由于在碎时间下写出，所以可能会有很多冗... -
决策单调性_成型笔记
决策单调性 警告：本篇中关于“二维凸性”的描述有误，四边形不等式并不意味着二维凸性，这种性质被称为矩阵的蒙日性，是极为高阶的内容，感兴趣者可以自行搜索。 但这个错误对本篇的应用价值没有损害，在怀疑一个问题有决策单调性时，更多地我们会去观察贡献形式，... -
后缀数组_成型笔记
后缀数组 后缀数组，启动！ 我发现大家学习算法的路径都是先打模板，然后练题，然后完全掌握，然后学习下一个算法。 但是我的算法学习是先把所有算法的模板抄一遍，然后过了两年看到自己 A 掉了模板想起来原来自己还学过这个东西。 虽然 SAM\text{SA... -
图计数矩阵树_成型笔记
图计数 矩阵树 图论和线性代数的边界之处。 高斯消元求行列式 LGV\text{LGV}LGV 引理 矩阵树定理 BEST\text{BEST}BEST 定理 高斯消元求行列式 123456789101112ll gau() {ll r... -
回文系列_成型笔记
回文系列 回文系列。 对于一个静态串，描述其回文性质的重要信息是回文半径，此处不区分奇偶回文，已知奇回文算法求偶回文只需添加分隔符，已知偶回文算法求奇回文只需复制字符。 求回文半径的通用方法是二分 + 哈希，需要求正反哈希，不要傻傻的用一个哈希做，复... -
快速沃尔什变换_成型笔记
快速沃尔什变换 其实是不太想接触这类东西的。 但是万一他就考你个子集卷积呢？万一呢万一呢？万一 Θ(3n)\Theta(3^n)Θ(3n) 比 Θ(2n)\Theta(2^n)Θ(2n) 少很多昏呢？ 可能大概或许是把 command_block’... -
后缀自动机_成型笔记
后缀自动机 之前听人说 SA\rm SASA 能把很多问题变成数组上的问题，但 SAM\rm SAMSAM 变成的是树上问题，数组问题比树上问题好做。 但是我用 SA\rm SASA 从来都没有 SAM\rm SAMSAM 好用。 思考一下原因的话可... -
排列（置换群Polya定理）_成型笔记
排列（置换群 Polya定理） 在通常的理解中，置换是一个元素两两不同且长度与值域大小相同的数组，但将置换看作“可运算的元素"是更本质的理解。 定义 a∗ba*ba∗b 这个运算得到的排列为满足 ∀i,pi=bai\forall i,p_... -
特征多项式_成型笔记
线性代数。 为什么要学这个？都是矩阵树惹的祸。 本篇同时作为 ABC323G 的题解。 注：由于本篇写就的时候题解区只有一篇高深莫测极其简短的题解，看了半天没看懂又跑去学特征多项式，结果特征多项式题解也看了好久才看懂，所以笔者决定整理一篇详细易懂的... -
线性规划对偶_成型笔记
线性规划对偶 刚刚去瞅了眼 HLPP，又去瞅了眼 KM，感叹还是学理论好。 概念 线性规划是在对一些实数变量的线性不等关系约束下，求解一个线性表达式的最值的过程。 标准型： max:∑jcjxjs.t. ∀i,∑jai,jxj≤bi∀j,xj≥0\... -
（暴力）多项式与生成函数_成型笔记
多项式与生成函数 由于快速傅里叶变换并不在 CCF 的考纲之内，故对于多项式的考察仅限于公式推导。 即使是只剩下公式推导，多项式仍然是一个强大的工具。 多项式暴力全家桶 以下很多东西是在 mod xc\bmod\ x^cmod xc 意义下定义的... -
O(nlogn)支配对_成型笔记
O(nlogn)\cal O(n \log n)O(nlogn) 支配对 初始有 nnn 个对象，两两可以产生一个贡献，每次问区间点对贡献的合并。 如果维护两两贡献，则复杂度为 Θ(n2)\Theta(n^2)Θ(n2)，无法接受。 但有的时候题目... -
倍增值域分块_成型笔记
倍增值域分块 带 log\loglog 时间复杂度的均摊，可以分出两种常见的类型： 每个数被操作一次之后就会减半。 每个数被操作一次之后可能减小的很少，操作很多次后减半。 对于第一种问题，难点在于如何高效找到每次操作，有哪些数需要被减半。 对于... -
广义串并联图_成型笔记
广义串并联图 我觉得一个 noip\text{noip}noip 二等人来学这个就是玩原神玩的。 本来一直念叨着想学，然后前两天： 下面的讨论均基于无向连通图。 形式化标准定义：不存在与 K4\mathbb K_4K4 同胚的子图的图（没什么用... -
吉司机线段树_成型笔记
吉司机线段树 需要注意，如果仅仅是区间取 max\maxmax，区间取 min\minmin，区间求 max\maxmax，区间求 min\minmin，区间加，这是可以单 log\loglog 的，只有求区间和这种阴间东西的时候才需要 b... -
线段树全家桶_成型笔记
线段树全家桶 简单的东西通常蕴含着深刻的道理。 这大概并不是一篇入门博客，而是一篇较为完整的梳理。 并不会有太多的例题，只有强烈凸显算法特点的例题会被展示。 目录： 简介：线段树维护的信息 线段树写法/技巧 框架 动态开点 可持久化 标记永久化 ...
璀璨的星河,｜
我何时成为你的一颗？｜