提高组模板大全

整点板子
更新：新增了数学里的几个没怎么考过的板子，删去了树剖板子
有建议找 YLF_Cat

说明

P5905 是 Johnson 板子，可用于验证 Floyd 正确性
莫队不属于提高组考点，但是可以拿来乱搞，遂加上
含有一些没怎么考过但是的确在 NOI 大纲里的算法，主要在数论那块

[图论]

  • Dijkstra
  • SPFA（bellman-ford）
  • Floyd
  • 传递闭包
  • 差分约束
  • LCA
  • 树剖（这个怎么是 NOI 级的，删了）
  • Tarjan 缩点
  • 树上差分
  • Kruskal
  • 欧拉路（没怎么考过）
  • 树的重心 直径

[字符串]

  • KMP
  • Hash
  • Manacher
  • Trie

[数据结构]

  • 树状数组
  • 线段树
  • 笛卡尔树
  • ST 表
  • 单调栈
  • 单调队列

[动态规划]

  • 各种背包
  • 树上 dp
  • 区间 dp
  • 状压 dp

[数学]

  • 线性筛
  • 矩阵快速幂
  • 逆元
  • 预处理全家桶（没有这个的板子）
  • 卡特兰数
  • 高斯消元（没怎么考过）
  • 中国剩余定理 crt（没怎么考过）
  • 扩展欧几里德算法 exgcd（没怎么考过）
  • 裴蜀定理（没考过）

[杂项]

  • 扫描线
  • 离线二维数点
  • 离散化
  • 莫队
  • 逆序对