- 树剖求lca
- 第二类Stirling数
- 倍增+floyd 跑路【G[i][j][logn] 和 dis[i][j]的巧妙定义】
- spfa 负环 多组要建图的数据记得mem(head,0),记得初始化cnt[s]=1;,cnt[v]>n而不是>=(容斥原理)
- 欧拉图 考虑：1.连通 2.欧拉图的判定
- st表
- 会议座位 以第一个序列作为基准，用数组x映射一下b在a的位置，那么总不满值就是新的编号的b的逆序对个数
st 表
rep(i,1,n)rd(f[i][0]);
rep(j,0,20)
for(int i=1;i+(1<<j)-1<=n;++i)
f[i][j+1]=max(f[i][j],f[i+(1<<j)][j]);
while(m--){
int l,r;rd(l),rd(r);
int len=log2(r-l+1);
printf("%d\n",max(f[l][len],f[r-(1<<len)+1][len]));
}欧拉图
*如果图中奇数度的顶点个数小于等于2，则一定存在欧拉回路
*在无向图中每个顶点的度都是偶数，则一定存在回路
*在有向图中，每个节点的入度等于出度，则存在回路
使用并查集维护经过点的个数
设hebing为成功合并的次数,n为点数
则整张图含欧拉路当且仅当hebing>=n-1且奇度数点为0或2
//tot:出现的点的个数（把一种颜色看做一个点）
//hebing记录成功合并的次数
【第二类Stirling数】P1287 盒子与球
表示n个球放入r个不同的盒子的方法。
状态设定：设
f[i][j]表示前i个球放入j个盒子的方法
答案表示：
f[n][r]* fac[r](最后的最后，由于是r个不同的盒子，所以要×*r!)
状态转移：f初始化为1,
f[i][j]=f[i-1][j-1]+j*f[i-1][j]
1.考虑第i个球不放入j-1个盒子，而是新开一个盒子（f[i-1][j-1]前i-1个已经放好在了前j-1个盒子，第i个放入新的j号盒子）
2.考虑第i个球放入已经选好的j个盒子.（
j* f[i-1][j]前i-1个已经放好在了前j个盒子，第i个放入选好的前j号盒子的任意一个，所以要* j）