悬线法可以用来解决给定矩阵极大子矩阵问题。 洛谷P4147玉蟾宫 这题本质上就是给定一个矩阵，有一些格不能选，求能选的最大的子矩阵大小，可以用悬线法来解决。 悬线，指的是从某一点向上出发，不穿过任何障碍格的垂直线段。比如下图中的几条悬线： 有一个结论：最大子矩阵一定可以通过某条悬线向左右拓展而成（可能有多条可能的悬线）。其实这个结论也很好证明，因为矩阵一定是被框在边界或障碍物之间，那么拓展成这个矩阵的悬线就是到其下界在框它上面的障碍物的那条线，否则一定有更优的矩阵。 知道了这个，我们就可以枚举每一条悬线，求出它能拓展的最大矩阵求个\(\max\)。由于只有\(nm\)条悬线，所以理论上是可以...

割点 定义：在无向图连通图中，若把点\(x\)删去后整个图就不连通了，则\(x\)为割点（割顶）。 朴素方法：每次删去一个点，然后判断图是否连通，时间复杂度为\(O(n(n+m))\)。 Tarjan算法： \(dfn_x\)：\(x\)被dfs到的时间戳 \(low_x\)：在\(x\)及以后被搜索的所有节点的\(low\)值和这些节点能到达的节点的\(dfn\)的最小值。 算法流程： 从\(1\)号点开始遍历全图，对于遍历到的点\(x\)，记录它的\(dfn_x\)并将\(low_x\)的值赋为\(dfn_x\)。 接下来遍历\(x\)的所有子儿子\(y\)： 若\(y\)被访问过，...

单调栈 以这道题为例：P5788。我们考虑维护一个单调栈，里面存的是下标，使里面的下标对应的元素从栈顶到栈底是单调上升的。 我们从\(n\rightarrow1\)枚举\(a_i\) 对于每个\(i\)，如果栈非空，令栈顶的下标为\(j\)，若\(a_j\)不比\(a_i\)大，那么这个栈顶元素由于值又小，位置又靠后，如果\(j\)能满足的条件，\(i\)也一定能满足，而且\(i\)适用范围更广，所以\(j\)不可能成为之后的的\(f_i\)，所以就将这个元素弹出。 重复以上操作直至\(a_j>a_i\)，此时的栈顶就是\(f_i\)。其实这也能解释为什么不符合元素的栈顶要出栈：如果不...

树状数组是一种数据结构，普通树状数组维护的信息及运算要满足结合律且可差分。 一维树状数组 单点加、区间求和 树状数组是用长度为\(n\)的数组存储的。我们假设这个数组为\(n\)，令lowbit(i)=i&(-i)，则\(c_i\)保存的是向前lowbit(i)长度的\(a\)数组区间和。 单点加：从\(i\)开始，修改所有包含\(a_i\)的\(c_i\)：\(c_i,c_{j=i+lowbit(i)},c_{j'^=j+lowbit(j)}\)…… 区间求和\([1,x]\)：累加\(c_x,c_{x'=x-lowbit(x)},c_{x''=x'-lowbit(x')}\)……...

持续更新中 索引 1快读快写 1.0快读快写 2数据结构 2.0堆 2.0.0二叉堆2.0.1左偏树 2.1线段树2.2树状数组2.3st表2.4单调栈2.5单调队列2.6可持久化数据结构 2.6.0可持久化数组2.6.1可持久化线段树 3图 3.0图的遍历 3.0.0图的深度优先遍历3.0.1图的广度优先遍历 3.1最短路 3.1.0floyd3.1.1spfa3.1.2dijkstra（堆优化） 3.2图的连通性 3.2.0割点3.2.1割边3.2.2点双连通分量3.2.3边双连通分量3.2.4强联通分量 3.3图匹配...

左偏树属于可并堆的一种，可并堆，也就是可以在较低的时间复杂度下完成对两个堆的合并。 定义及性质 对于一棵二叉树，定义外节点为左儿子或右耳子为空的节点，定义其的\(dist\)为\(1\)，而不是外节点的\(dist\)为其到子树中最近的外节点距离\(+1\)。空节点的\(dist\)为\(0\)。例如，对于这一棵二叉树，其的外节点和\(dist\)如下： 定义：有一棵二叉树，如果它不仅满足堆的性质，对其的每一个节点都有左儿子的\(dist\)大于等于右儿子的\(dist\)，则称其为“左偏树”。为什么会“左偏”呢？不妨举几个例子： 其中，前两个为左偏树，可以发现，它们确实是向左偏的；而后两...

扫描线可以用来求解周长并和面积并。 面积并 扫描线 给定\(n\)个长方形，求它们的面积并。下面以两个长方形为例： 对于这个问题，可以有容斥等做法，但是还有个更简单的方法——扫描线。 扫描线，顾名思义，就是，拿一条“线”取扫（这里是从下往上扫，其实其它的扫的方式也是可以的）： 如图所示，这几个图形被四条线分成了\(3\)个部分，我们可以对每一个部分的面积计算并累加起来。由于这些部分都是长方形，而这些长方形的宽很好计算，就是线扫过的距离（图中橙色箭头所标），而要求的就是长方形的长。 把每个矩阵的下面的边的值记作\(1\)，上面的边值记作\(-1\)，每次经过值为\(1\)条边就把对应边加进...

PS：本文仅起一个备忘的作用。 set set指的是有序的不可重集，与数学上的定义类似。 常用操作： p.insert(x)：在\(p\)中插入\(x\)，若\(p\)中已有\(x\)则返回false，否则返回true p.erase(x)：在\(p\)中删除值为\(x\)的元素，返回删除的元素个数 p.erase(pos)：在\(p\)中删除迭代器为\(pos\)的元素 p.clear()：清空\(p\) p.begin()：返回指向\(p\)首元素的迭代器 p.rbegin()：返回指向\(p\)末尾元素的迭代器 p.end()：返回指向\(p\)最后的占位符的迭代器，没有元素 p.co...