-
有向图的强连通分量
定义：给定一张有向图。若对于图中任意两个节点 ，既存在从 到 的路径，也存在从 到 的路径，则称该有向图是 “强连通图” 。有向图的极大强连通子图被称为 “强连通分量“，简记为 。 如图，红色部分即为一个 。 Tarjan算法：实现原理：1... -
主席树
概念：主席树的全称为可持久化权值线段树，用于维护每一个数在插入线段树后的历史版本，从而进行区间 大数查询等操作 基本形态：如果为每一历史版本新开一棵线段树，空间复杂度将达到 ，是不可接受的 而对于一棵线段树，每一次操作仅会对树上的一条链产生影响，所... -
快读
getchar_unlocked()快读getchar_unlocked() 的速度比 fread() 略逊一筹，但是有代码短小精悍的优点，可以在比赛中直接使用 12345678910namespace getchar_unlocked_fastre... -
LCA--最近公共祖先
最近公共祖先:对于有根树T的两个结点u、v，最近公共祖先LCA(T,u,v)表示一个结点x，满足x是u和v的祖先且x的深度尽可能大。在这里，一个节点也可以是它自己的祖先。 (一)的倍增算法:倍增算法：倍增法求实质上是用二进制拼凑出两个节点的最近公共祖... -
最短路
从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径叫做最短路径。 最短路算法根据应用场景，可选用Dijkstra算法、spfa算法和Floyd算法 1.算法：算法是一种基于贪心的单源最短路算法，有朴素与堆优化两种 证明：f... -
Splay
简介：Splay树 或 伸展树，是一种平衡二叉查找树，它通过 Splay操作 ，每操作一个节点，就将该节点旋转 (双旋) 至根节点 ( 这样既可以保证其时间复杂度，又可以保证其维护值的正确性 ) ，使得整棵树在仍然满足二叉查找树性质的同时，可以使树保... -
树状数组
推导：已知一个数为 设其二进制表示为： 其中有 所以这个数可以划分为以下几个区间：我们已知以下条件： 表示二进制表示的最后一位 表示二进制表示的倒数第二位，以此类推 所以对于以上区间中的任意区间，都有长度一定是的二进制表示的最后一位所对应的... -
线段树
要素：线段树的定义一般用结构体定义 1234struct Node{ int l,r; // 左右儿子 int // 需要维护的量}tr[N*4]; 基本操作：1.build(u , l , r)建立一棵线段树 通用代码：12345678... -
C++后缀表达式
引进概念中缀表达式：即一般的表达式 eg. a+b*c/d*(e-f) 后缀表达式：即将中缀表达式中的运算符置于操作的数字后 eg. abc*d/ef-*+ 中缀表达式–>后缀表达式运用一个栈，一个队列，分别用来 临时 存放运算符和...
1