随笔索引

如题，仅收录2021年9月以后的博客园上的随笔，毕竟在此之前的随笔不太好弄。按知识点分类。

1.数据结构

• 树状数组&线段树

线段树优化统计过程，我的方法和基站选址异曲同工。
一道比较巧妙的题目。
一道比较简单的构造题，线段树起构造解的作用。
一道公式题，把式子推出来后没那么难。

• 分块&块状链表

比较水，可以用lct来做。
块状链表&值域分块模板。块状链表的解法比树套树常数小跑得快。

• 平衡树（Treap，Splay，无旋，替罪羊等）

Splay的模板。
平衡树的模板。
平衡树维护序列模板。
同上，只不过更复杂一点。

• 树套树&K-D树

线段树套平衡树模板。
K-D树维护二维数对的模板。

• 可持久化数据结构（主席树等）

• 为合并而生（左偏树，线段树合并等）

左偏树（可并堆）的模板，用到了一丢丢贪心。
线段树（动态开点的权值线段树）合并模板。

2.图论

• 最短路

玄学题目。
“最短路生成树”的应用。
对于一些题目的总结。

• 强连通分量（包括2-sat），割点&桥

• 二分图

模板。

• 生成树

• 最大流，最小割&费用流

模板。
模板。
比较简单的网络流建模题目。

3.树

• 重链剖分&长链剖分

离线处理，重链剖分题目。
一道简单的树链剖分题目，不知为何评紫。
长链剖分模板。

• 实链剖分（LCT）

模板。

• lca相关

4.动态规划

• 线性DP&区间DP

一道稍稍有些暴力的题目，线性DP+二分。
区间DP，有一点思维难度。

• 树形DP（包括虚树&换根）

换根DP模板。
树上背包问题，要注意枚举顺序。
虚树模板。
虚树模板。

• 期望&概率DP

简单图上期望DP。

• 决策单调性优化DP&斜率优化DP

第一种二分写法的决策单调性优化DP。
分治写法下的决策单调性优化DP。
模板。
一道题解区都用的斜率优化写的题目被我用决策单调性钢出来了。

• 数据结构（包括单调队列）优化DP

5.字符串

• 回文相关（manacher，回文自动机等）

• Trie（包括01trie）

01Trie应用，有思维难度，解法很巧妙。

• kmp&AC自动机

• 后缀数组&后缀自动机

模板。
后缀数组的height数组的基本应用。

6.贪心

质因数分解剔除多余部分后贪心。
一道比较巧妙的贪心，考场上手残扣了12分。
奇怪的题目。

7.数学

• 线性基

线性基模板。
线性基加上贪心。
了解了Nim游戏的结论之后就变成了一块可可爱爱的板子啦。

• 高斯消元（包括矩阵周边）&拉格朗日插值

高斯消元的模板。说实话感觉这个算法有点故作高深。

• 其它的数学题目

混进来了一个奇怪的东西……
推式子题目。

8.计算几何

9.博弈论

• 简单博弈论问题

经典博弈论问题。

10.其它算法

• cdq分治&线段树分治

三维偏序板子。
四维偏序板子。

• 整体二分

整体二分板子。

• 莫队

四种莫队（普通莫队，带修莫队，回滚莫队和树上莫队）初学总结。

• 树分治

树分治模板题。