并不是HH的项链主要原因是,洛谷的HH项链卡莫队卡的很严重,而我又是初学莫队,所以说就不去挑战了 而且HH的项链树状数组写码量也没太大的区别 对于初始维护首先考虑O(nm)的: 对于m次询问,每次我可以维护一个cnt数组…

CDQ分治,总而言之就是很神奇的分治 在这里引入二位偏序问题(逆序对) 对于一位偏序的解决方法可以理解为CDQ分治(归并排序) 对于二维偏序也就是逆序对可以用树状数组统计,也可以用归并排序统计 对于归并排序就是每次合并两…

树套树, 这个东西我想学了好久了,之前虽说一只在听说线段树里套个set就是树套树,(一只也是这样认为的)但是我写树状数组套主席树的时候总感觉有那里很迷惑,去找dalao想要问问具体的实现方法 然后被dis回来,接下来就咕…

普通的Treap已经在我草稿箱里面带了快五个月了,咕咕咕 这篇文章就讲非旋Treap, 在一些比较正常的平衡树的题中非旋Treap相对于Splay,有代码量更少,细节更少,更好差错等诸多有点,因此除非必要情况我一般来说还…

一个咕咕咕了很久的算法, 众所周知扫描线就是维护y轴(或x轴)同时存在的的线段的总长度, 然后按照x轴从大到小的遍历x,很容易就能想清楚,对于一个按顺序排列的x,每次我都可以跳这一段距离,而不会导致中间的某一个区域突然需…

题目链接 题目 人们发现一份字典序未知的单词表。其中共包含 nn 个单词。 虽然不知道具体的字典序，但大家已知这些单词在单词表上是按照字典序排列的。 你需要求出这份单词表所依照哪种字典序。 思路 同样是一份字典树的写法,…

题目: 一个长度为 n 的环形 DNA 序列，以顺时针顺序给出，其中每个基因有类型和编号两个属性，类型是 s（头）或 e（尾）中的一种，而编号是 1 到 106​ 中的整数。 你需要在某个地方切断，按照顺时针顺序拉成链后…

李超线段树，又是一个神奇的线段树 模板题大意: 对区间等差数列取max(min) 题目翻译: 对一个平面直角坐标系，我对于区间插入很多条直线(线段),然后询问当在某个点时y的最大值 维护这个区间内的所有直线中，从上往下能…

我一直认为数据结构就是最优雅的暴力,虽说我实在认识到了这件事情之后才接触的这个东西,不过他也加深了我对这句话的理解 首先对于一个有条件的修改该如何处理? 当然我是第二次做类似的题,第一次是每次区间修改操作是如果区间内一个…

本文代码是我临时手打的,没有测试,并不保证细节上的正确性 首先线段树是一个性质非常好的一棵树,因此在线段树的神仙的操作就会有很多 首先对于一颗线段树如果我们需要操作去查找历史版本的话,那样就需要可持久化了, 首先需要历史…