左偏树 一种可以合并的堆 前置知识 dist 对于一棵二叉树，我们定义 外节点 为左儿子或右儿子为空的节点，定义一个外节点的 为 ，一个不是外节点的节点 为其到子树中最近的外节点的距离加一。空节点的dist为0。 那么左偏树就是一颗满足堆的性质的二叉树，它的左儿子的dist大于等于右儿子的 核心 核心操作是合并，合并到时候，要满足堆得性质，对于小根…

Treap treap是啥，是一种平衡树，tree+heap 众所周知，二叉平衡树一旦退化，复杂度将会很可怕。 treap则给每一个节点附上了一个随机的值，然后利用旋转操作，让这个二叉搜索树同时也满足堆的性质。期望下可以达到$O(nlog_n)$的复杂度了。 具体怎么实现呢 大部分的操作和一般的二叉搜索树一样。 插入 void insert(int…

Lisa 显然的贪心思路就是用田忌最大的和齐王最大的进行比较，如果不能，就从小到大找到第一个没有贡献的马，用它换掉最大的 马，重复以上操作 什么叫没贡献的马，最弱的马和最弱的马进行比较，如果田忌的最弱的赢不了，他就是没贡献的 为什么不能简简单单的去最垃圾的马去换 这样可能造成不必要的浪费，既然他能做出贡献，有为什么要用来换呢 比如说对于这组数据 1…

wqs二分时间 给定 个物品，我们需要在其中恰好选择 个，并且需要最大化收益。设对应的收益为 ，那么需要满足在最大化收益的前提下，每多选择一个物品，额外产生的收益是单调递减的，也就是 。同时，如果我们对物品的选择数量没有限制，即 不存在，那么我们应当能够快速地计算出最大的收益，以及达到最大的收益需要选择的物品数量 wqs二分的使用通俗的理解就是(个…

jisoo 典型的CDQ分治 一维的时候比较就行了 二维的时候加一个数据结构，就像逆序对一样 三维的时候则需要，使用CDQ分治来解决了 首先把全局按照第一维从小到大排序，相同的按照第二维，还相同的按照第三维 然后开始从中间分开，分治。 显然这个过程位于 $mid$ 两边内部的都会在自己的过程中被解决，新的贡献来自于跨过mid的比较。 这一部分怎么处…

Lisa 贪，就硬贪 显然当权值最大的那个点可以选了之后，必须立马选它答案才会最有 既然这个点必须立即选的话，那么何不把它和父亲合并起来，取个平均值 然后这颗新树上重复这个操作 就可以得到一个染色的顺序 #include<iostream> #include<cstdio> #include<cmath> #in…

Lisa 对于这样的贪心题，很容易想到按照某个顺序排个序，比如说最小的spfa值递减 因为这样的话，对于每一瓶防晒霜，要不前面的牛能用，要不只有前面的牛能用 这样为了给后面省出尽可能多的防晒霜，不如把能用的最大的给前面的牛 也确实如此 #include<iostream> #include<cstdio> #include&…

Miku hash一波 然后拉链法散列表 #include<iostream> #include<cstdio> #include<cmath> #include<vector> #include<algorithm> using namespace std; template<cl…

Miku 如果我们知道哪两个点可以用跑路机1s到达就好办了 怎么知道呢？如果两个点的距离可以为$2^k$,那么一定有一个中转接点，到两个点的距离都是$2^{k-1}$，也就是如此了。 这样显然可以用$floyd$预处理出来距离 #include<iostream> #include<cstdio> #include<c…

Miku 这个题可以用树hash做 怎么搞呢，对于一棵树，我们要用hash记录他的形态 对于二叉树，我们要记录的就是左儿子的hash和自己和右儿子。 然后进行比较 我采用的是对于左右儿子和自己乘上不同质数的方式 还有自然溢出，以及两次hash #include<iostream> #include<cstdio> #incl…