主席树学习笔记 前置芝士 线段树 动态开店线段树 权值线段树 脑子 pvz 玩多了 用处 主席树即可持久化线段树，在线段树的基础上可以查询修改每个修改的内容并形成新的版本。 思想 如果每次修改后在建一棵线段树，空间复杂度肯定受不了。注意到线段树的一次修改操作最多影响 log⁡\loglog 个节点。因此我们可以只新建修改的节点，将原来的节点也用上，这样空间复杂度就是 Θ((n+q)lo

CF367E 题解 有 nnn 个区间，你需要为每个区间分配左右端点 lll，rrr (1≤l≤r≤m1 \le l \le r \le m1≤l≤r≤m)，使得区间两两互不包含且至少存在一个区间 的左端点等于 xxx，输出方案数对 109+710^9 + 7109+7 取模的结果。 1≤n,m≤1051 \le n,m \le 10^51≤n,m≤105, 1≤x≤m1 \le x \le

线段树合并学习笔记 前置芝士 动态开点线段树 一般我们写线段树都是在刚开始调用一个 build 函数建立出所有节点。但实际上有很多节点并没有保存信息，这些节点是多余的。所以就有的动态开点线段树，只有在用到时才建立这个节点，这种思想节省了很多空间，节点与节点之间的灵活性也更高，为线段树合并和主席树等算法提供了基础。我们简单了解一下动态开点线段树的代码实现。 线段树节点不同于普通线段树，需要存储

浅谈序列自动机 link 序列自动机是淦什么的 序列自动机好高级的名字用于解决子序列问题，可以在线性时间判断串 TTT 是否是串 SSS 的子序列，这篇文章主要介绍两种方法实现。 做法 1 我们求出一个数组 fi,cf_{i,c}fi,c​ 表示在模式串 SSS 中位置 iii 后字符 ccc 第一次出现的位置。这个很简单，我们倒序枚举 SSS，从 i+1i + 1i+1 继承值并更新。 f

三元环计数问题 link，给定一个无向图，求其中三元环的数量。 1≤n≤1051 \le n \le 10^51≤n≤105，1≤m≤2×1051 \le m \le 2 \times 10^51≤m≤2×105 。 构造一个这样的有向图：对于原来图中的每一条无向边，改为由度数小的向度数大的连边，若相等则由编号小的向编号大的连边，在这样的图中，三元环 {x,y,z}\{ x,y,z\}{x,

P3306 题解 link，给出 ppp，aaa，bbb，x1x_1x1​，求第一个 xi=tx_i = txi​=t。 xi+1≡a×xi+b(modp)x_{i + 1} \equiv a \times x_i + b \pmod{p}xi+1​≡a×xi​+b(modp) 。 0≤a,b,x1,t<p0 \le a, b, x1, t < p0≤a,b,x1,t<p，

BSGS（大步小步）算法学习笔记 前置芝士 会取模运算就行啦！ 正文部分 拔山盖世 BSGS\tt{BSGS}BSGS 算法用于求解 ax≡b(modp), a⊥pa^x \equiv b \pmod{p}, \ a \perp pax≡b(modp), a⊥p 中 xxx 的值。 设 x=ti−jx = ti - jx=ti−j，t=⌈p⌉t = \left \lceil \sqrt{p}

exgcd（扩展欧几里得）学习笔记 前置芝士 基础的模、整数运算； gcd⁡\gcdgcd 的求法，即 gcd⁡(a,b)=gcd⁡(b,a mod b)\gcd(a, b) = \gcd(b,a \bmod b)gcd(a,b)=gcd(b,amodb)； 裴蜀定理，二元一次方程方程 ax+by=cax+by=cax+by=c 有解的充要条件是 gcd⁡(a,b)∣c\gcd(a, b)

网络流 24 题 部分题题解 注：代码只给出主程序部分，网络流板子基本相同。 方格取数问题 link 给定 mmm 行 nnn 列的网格，每个格中有数，你可以取任意个格子的数，但不能同时取相邻的格子（四联通），求取出数的和的最大值。 1≤n,m≤1001 \le n,m \le 1001≤n,m≤100，1≤ai,j≤1051 \le a_{i, j} \le 10^51≤ai,j​≤105

网络流学习笔记 注：笔者比较菜，许多证明没有给出，一些地方可能有误。 一些定义 网络 对于一张有向图 G∈(V,E)G \in (V, E)G∈(V,E)，有一个源点 S∈VS \in VS∈V 和一个汇点 T∈VT \in VT∈V，每一条边 (u,v)∈E(u, v) \in E(u,v)∈E 有一个限流 c(u,v)c(u, v)c(u,v)。特别的，∀(u,v)∉E , c(u