呃呃，没想到还会有这种若只东西 好吧确实记不住呀……写一下： 1 2 3 4 5 6 while (l < r) { int mid = l + r >> 1; if (check(mid)) r = mid; else l = mid + 1; } 和 1 2 3 4 5 6 while (l < r) { int mid = l + r + 1 >> 1; if (check(mid)) l = mid; else r = mid - 1; }

好吧这是第二个紫模板算法 后缀自动机简介 一个对字符串所有子串进行高度压缩后储存的数据结构，其时空复杂度均为线性。 实际上可以理解为一个压缩了的后缀 Tire，因为共用了大量节点，所以 SAM 整体来看是一个 DAG。 概念 endpos 对于字符串 sss 的任意子串 ttt（含空串），我们记它在 sss 中结束位置的下标（从 111 开始）的集合为 endpos(t)endpos(t)endpos(t)。 特别的，空串的 endpos={1,2,…,∣s∣}endpos=\{1,2,\dots,|s|\}endpos={1,2,…,∣s∣}。 等价类 记 maxlenmaxlen

0x00 引入 给定主串与模式串 ，问主串中是否存在模式串。 实际上这是一个最为简单的字符串匹配问题，对于暴力匹配来讲，每一次匹配失败时将模式串后移一位从头开始匹配是 O(n2)O(n^2)O(n2) 的复杂度，显然不够优。 而观察会发现，上述的解法会有很多次不必要的匹配过程，而 KMP 则可以减少匹配次数，Z 函数则是用另外的方法对更多信息进行处理，经过适当转换也可解决上述问题。 0x01 KMP 对与上图的情况，我们假设 1、2、3、4 部分是一样的，那么我们在 jjj 处发现 tj≠sit_j \ne s_itj​=si​ 时，由于 1，2 部分相等，可以让 jjj 回退到

建议在右侧的设置按钮中打开阅读器模式阅读 可能是学过的唯一一个紫模板算法吧 虽然基于 Splay，但是并没有 Splay 难调 LCT 简介 LCT 是一种解决动态树问题的算法，就是在树链剖分的基础上可以断开或连接边（当然保证还是一棵树）。 那么对于这种问题，自然就不能用重链剖分来解决，这时便需要一个新的组合——实链剖分+Splay 模板题看这里 实链剖分 对于一个点连向它所有儿子的边，我们自己选择一条边进行剖分，我们称被选择的边为实边，其他边则为虚边。对于实边，我们称它所连接的儿子为实儿子。对于一条由实边组成的链，我们同样称之为实链 —— Oi-Wiki Splay 先放两篇博客

下文中以 ⟨⟩\langle\rangle⟨⟩ 表示矛盾的集合，[][][] 表示题目给定的的集合 定义 2-SAT，简单的说就是给出 nnn 个集合，每个集合有两个元素，已知若干个 ⟨a,b⟩\langle a,b \rangle⟨a,b⟩ ，表示 aaa 与 bbb 矛盾（其中 aaa 与 bbb 属于不同的集合）。然后从每个集合选择一个元素，判断能否一共选 nnn 个两两不矛盾的元素。显然可能有多种选择方案，一般题中只需要求出一种即可。 ——来自oiwiki 解法 对于 2-sat 问题，我们可以将它抽象成一个图论问题，建图来完成。 建图 首先考虑如何建图，对于两个集合内 [a,b

高斯消元 给定一组 nnn 个未知数的方程组，有 nnn 个方程 {a1,1x1+...+a1,nxn=b1...a1,1x1+...+an,nxn=bn\left\{\begin{matrix} a_{1,1}x_{1} + ... +a_{1,n}x_{n} = b_{1} \\ ... \\a_{1,1}x_{1} + ... +a_{n,n}x_{n} = b_{n} \end{matrix}\right.⎩⎨⎧​a1,1​x1​+...+a1,n​xn​=b1​...a1,1​x1​+...+an,n​xn​=bn​​ 转化到下面的表格 x1x_{1}x1​x2x_{2}

数位DP 引入 给你数字l、r，求l到r之间有多少个数 弱智题？ 方法一 从 lll 开始，暴力枚举到 rrr , 时间 Θ(n)\Theta(n)Θ(n) 方法二 公式， ans=r−l+1ans = r - l + 1ans=r−l+1 方法三 ans=res(r)−res(l−1)ans = res(r) - res(l - 1)ans=res(r)−res(l−1) resresres 如何求？ 数位dp！！！\Huge 数位dp！！！数位dp！！！ 核心思想：按字典序由高位到低位计算 看图 -43210-656430123456…求 000 到 656436564365