Category Archives: 板子

旋转卡壳

最近准备搞搞几何,这次拿旋转卡壳开刀,来一发学习链接:666 1. 旋转卡壳计算凸包上两点距离最大值(凸包的直 …

回文自动机

学习了一种对付回文问题的一个强有力的工具,回文自动机,和manecher功能是一样的,但是会更加的强大好用,就 …

自定义日期类

 

KM算法

二分图带权匹配

 

多重匹配

 

二分图 — Hopcroft-Karp 算法

为了降低时间复杂度,可以在增广匹配集合M时,每次寻找多条增广路径。这样就可以进一步降低时间复杂度,可以证明,算 …

LCA,RMQ-ST算法

dfs根据将路径经过的点存下来,那么树就变成线性的,对于任意两个点的lca就是这两个点在数组中第一次出现的位置 …

树链剖分解决LCA

明白树链剖分原理的应该会明白,其实每次询问都是将分段好的两条进行整合,整个过程其实就是LCA的过程。 核心代码 …

LCA离线算法

将询问存下来,在dfs过程中对其操作。我们不妨对走过的节点进行染色,如果从父亲经过孩子,那么孩子染成灰色,当回 …

两圆面积相交