Blog
I use blog to record something.
平衡树Treap
二叉查找树 给定一颗二叉树，树上每个节点都带有一个数值，称为该节点的“关键码”，所谓“BST性质”指的是： 1.该节点的关键码不小于它的左子树中任意节点的关键码； 2.该节点的关键码不大于它的右子树中任意节点的关键码。 满足上述性质的...
树链剖分
Introduction 树链剖分，计算机术语，指一种对树进行划分的算法，它先通过轻重边剖分将树分为多条链，保证每个点属于且只属于一条链，然后再通过数据结构（树状数组、SBT、SPLAY、线段树等）来维护每一条链。 ...
欧拉回路
定义 欧拉回路：图G中经过每一条一次边并且仅一次的回路称作欧拉回路。 欧拉路径：图G中经过每一条边一次并且仅一次的路径叫做欧拉路径。 欧拉图：存在欧拉回路的图叫欧拉图 半欧拉图：存在欧拉路径但不存在欧拉回路的图叫半欧拉图。 判断 定理...
luogu P3959 宝藏
题面 参与考古挖掘的小明得到了一份藏宝图，藏宝图上标出了 $n$ 个深埋在地下的宝藏屋， 也给出了这 $n$ 个宝藏屋之间可供开发的 $m$ 条道路和它们的长度。 小明决心亲自前往挖掘所有宝藏屋中的宝藏。但是，每个宝藏屋距离地面都很远...
luoguP3387 【模板】缩点
题面 题目描述 给定一个n个点m条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。 允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。 输入输出格式 输入格式： 第一行，n,...