P4364 九省联考2018 IIIDX 题意：n个摆成一根直线的盒子，有依赖关系（连续的盒子的父亲是一个盒子），你有n个带编号的球（编号可能相同），要放在盒子里面，要求一个盒子的编号要大于其父亲的编号，并且要求序列顺序…

线段树NB 李超线段树:维护最优势直线(选定x的时候y最大/最小的线段) 下面我们维护最大值 开一棵x范围的线段树,然后线段树的每个节点记录这个区间中点最高的线段(x = \frac {(l + r)} 2) 维护时考虑…

洛谷题面 题目大意 给定一个整数数列，求所有子区间中区间和前k大的区间的区间和的和（绕口令？） N\le 5\times10^5,k\le5\times10^5 分析 看到区间和，二话不说前缀和，这就没必要说了吧 然后考…

还是不把数据结构的总结文章的标题用\<算法>这种名字了...... 维基百科英文版的，这里的内容很多参考了那边：这里 （啊那个中文版太扯了） 左偏树满足堆结构，特点：可合并。声明：可并堆不止左偏树。 左偏树…

洛谷的题目链接 其实树剖的部分没难度，麻烦在最后一段的区间合并 ... 啊啊啊等会再说 我们先看看怎么定义一个区间： struct Node { int l, r, c[2], cnt;//l, r仅在线段树中使用 //…

注意了，LCT\not=动态树 当然没啥 建议这篇文章看两遍以后再去看看其他文章，反过来也OK，因为码风太毒瘤了... 当然指针的写法用来理解思想是很棒的 前言 树链剖分用的是重链剖分，我们把一棵树搞成了一条链，然后用一…

突然发现树链剖分应该不算算法？ 树链剖分：树\to链，方法：DFS序（dfn）。 前置问题： 将树从x到y结点最短路径上所有节点的值都加上z、求树从x到y结点最短路径上所有节点的值之和，在线 很好做对吧，树上差分，复杂度…

线段树大水题 但是这道大水题打了两天就对了。为什么？可以去看看这篇帖子。 线段树分别维护左右连续0/1段，区间最大0/1段，1的数量（0的数量可以直接算出），然后是推平和翻转的标记。 pushup在50行，老套路不想说了…

洛谷的题目链接 看起来要维护一个很动态的结果啊 但是查询操作只有一个max，并且插入也是插到最后的，所以我们直接来一个长度无限的初始序列，每个值均为最小值，然后插入改成把第x位改成某个数字，然后随便维护一下区间最大值什么…