~ Esoteria Algorithm in Reverse Observatory

幼儿园数学

CAUTION
This pointless post is intended for childern under six.

To begin with,watch this video.

线段树优化 Dijkstra

过早的优化是万恶之源。
Go beyond speed.

一般的 Dijkstra 使用 priority_queue 维护当前最短路的距离,但不吸氧气的 STL 性能表象不佳。维护当前最短路距离需要不断取出最小值,可以通过线段树查询最小值再修改为无穷大来模拟。

负环与单源最短路计数

Prologue

  • 若图上存在一个环,环上各边的权值之和是负数,则称这个环是负环。

负环判定

​设 cnt[v] 表示从 11vv 的最短路径包含的边数,cnt[1]=0。当执行更新 d[v]=d[u]+w 时,同样更新 cnt[v]=cnt[u]+1。此时若发现 cnt[v]>=n,则图中有负环。若算法正常结束,则图中没有负环。

轻重链剖分与树上路径操作

Prologue

前置技能

一些定义

  • 树上的路径称为树链
  • 非叶节点的儿子中子树大小最大的儿子为重儿子,其它为轻儿子
  • 从非叶节点到重儿子的边称为重边,其它为轻边
  • 由重边构成的链称为重链,其它为轻链
    • 重链中深度最小的节点为链顶
    • 重链的链顶都是其父节点轻儿子
    • 轻叶节点独自构成一条重链
  • 将树分割为重链和轻链即为剖分
  • 树链剖分就是用数据结构去维护重链和轻链
  • 左闭右开区间跟国际接轨

倍增 LCA

Prologue

给定一棵有根树,若节点 zz 既是节点 xx 的祖先,也是节点 yy 的祖先,则称 zzx,yx,y 的公共祖先。在 x,yx,y 的所有公共祖先中,深度最大的一个称为 x,yx,y 的最近公共祖先,记为 LCA(x,y)\text{LCA} (x,y)