主要用来写一些自己的漏洞

最大的漏洞：不记得更新这篇博客……

数据结构

Splay：（平均一个题4个小时我也是很服气

1. 一定要记得随时splay要不然会T（当然还得记得及时update不然在一些需要siz的操作会寄

2. 如果是区间翻转的时候，splay的时候要顺便pushdown，先pushdown父节点再pushdown自己（我也不知道为什么反正这样对反过来就错

3. （还有就是我的splay空间复杂度非常玄学，自己算算然后开数组就行了，能开多大开多大

4. 永无乡：在一个并查集里的东西要记得特判，不然就像我的splay一样所有的cnt都大于1了呜呜呜（然后就90分，我一直还以为并查集没啥错误来着真的是

LCT:（竟然一遍过了一次太nb了！

1. 区间翻转的时候，要开一个数组往上记录都要更新哪些点，然后把那些点拿出来都pushdown一遍，但是我总是忘了y = fa[y] 和top--

统计全局的tag，插入的时候减去tag，取出的时候加上tag

如果在求较大较小值的时候，设初值一定要好好设……能设多大（小）设多大（小）……

线段树记得开空间左移2，主席树要左移5

define int long long之前先算一遍空间

如果有区间加减到一定值删掉的操作，可以区间的值砍半挂到分治中心上做就是log得了

DP:

有很多的dp是有一些不能相邻一类的条件，这时候我们可以设状态表示现在又多少段，每个段怎么样的。。。

一个dp式子或者数学式子可以在交换求和号等等的交换情况下交换出来一个可以用前缀和优化的形式

有时候我们的dp是可以带着方程的系数进去敌退出来结尾的方程系数的（待定系数法）

区间dp很多时候都是$f_{i,j,k,l}$表示i-j区间之内的k-l的值域或者什么的，并且转移的时候k和l可以从k+1,l；k,l-1继承过来以减少复杂度

很多的dp是可以用段数表示状态的，然后往里放数字合并或者新加段

有的dp方程满足单调性可以用双指针单调转移

很多dp都不需要通过下标转移，一个状态可以表示这个状态的，类似于笛卡尔树dp？

本质不同二叉树个数为卡特兰数，不是阶乘……

二分答案！！！二分答案！！！要记得！！！

中位数一类的东西可以二分之后和>=0

数学

两个数的gcd一定小于等于他们的差

鸽巢原理！！！一定记住！！！

容斥：

小星星：如果说是一个排列，那么我们可以枚举点集为可以出现的点集，那么直接容斥就好了

概率：

如果说是一些出现或者不出现的东西，那么他们和的期望就是概率之和（权值为1

我们有时候可以把概率转化成一个左右两边转移过来的形式，那么我们有时候可以直接移项转成递推，也可以带状矩阵高斯消元

一个数字是可以用k个根号n和j个1拼出来的（k和j都小于等于根号n

当然还可以用二进制拼出来

一个东西的几次方在组合意义上面可以表示成取多少次然后相等

有的时候一些乘法的东西可以转化成log之后相加

有时候一些多项式的东西可以求导

枚举质数的时候一定要记得判大于等于根号的时候就可以停下来了啊啊啊啊啊啊

一定要记得break！！！！！！！！

凸函数加凸函数还是凸函数

如果一个连续函数满足：$f(x1)+f(x2)\le f(\frac{x1+x2}{2})$说明这个函数是个凸函数（琴生不等式）

左右移的时候记得转换类型

对球的颜色序列计数，只需要考虑，对于每一个颜色序列，判断它是否可行。

图论

一个图的dfs树没有横叉边，一个图的bfs树没有返祖边

满流并且在残量网络中找不到x到y的路径（即x,y在残量网络中不在一个SCC中），那么就是最小割的可行边

满流并且残量网络中源点能到入点并且出点能到汇点，就是说入点和源点在同一个SCC，出点和汇点在同一个SCC

强连通分量：low[x]==dfn[x]

无向边(x,y)是桥，当且仅当搜索数上存在 x 的一个子节点 y，满足：dfn[x] < low[y]

点双是：dfn[x]<=low[y]，不需要记录栈和vis数组

dfs栈出栈的时候有vis的情况下要清空vis（比如SCC）

点分治记得把rt设成0

所有生成树的边权和可以把一条边的边权变成$ax+1$的形式，a是边权，然后跑矩阵树定理求出来的多项式的一次项系数就是答案

如果进行拓扑排序的话，对于一个图，将其缩点之后得到的新编号的逆序就是一个拓扑序 CF798E

字符串

子串和子序列是不一样滴

后缀树可以SAM构建，SA想不到的题可以用后缀树想

manacher 和 exkmp 的时候记得和边界取min

SAM记得开两倍点空间，三倍边空间

其他

初始化

（记得开long long!!!!!!!!!!!!!!!!!!!!!!!，数组要开大！！！！！！！）

取max,min的时候记得转化成相同类型取

变量不要和关键字重复

要记得测极限数据看会不会TLE或者RE

记得特判一些特殊情况比如除0一类的东西

写题之前要先在草稿纸上面把步骤写下来，千万不要忘记步骤，就算是小步骤也不要忘……

好好看题

字符串转化成数字的时候要注意（有的时候字符集比较大）

哈希如果没时间写双模数哈希了可以求稳写双base

题目中给定的n和m不要写反

1e18以内的因数个数很少只有1e5

做不出来的题可以打表找规律

运算记得加括号，不确定的优先级一定要记得加括号

不要用endl！！！！！！！！！！！！！！！！！！会TLE！！！

string 类型s两种操作：s = s+'a'（复杂度O(N)）s+='a'（复杂度O(1)）

生成数据的生成器不需要输入的时候可以多用几遍……

三目运算符比if快到不知道哪里去了……我本地if2.5秒，三目运算符1秒……