神仙赛
T1:
? 神仙题
? 首先容易算出最高得分
? 考虑贪心的在得分不变的情况下选择最大的数
? 考虑如何快速算出删去一个数后能得到的最高分
? 考虑用权值线段树，每次合并节点的时候贪心的进行匹配
? 具体来说合并时我们可以用右侧的a匹配左侧的b，然后计入答案
? 这样用就可以用log的复杂度支持删除或加入一个数后计算最高得分
? 那么我们只需要一位一位的考虑过去，二分查找可以填的最大数，log复杂度check即可
? 复杂度\(O(nlog^2n)\)
?
T2:
? 神仙题
? 每次移动当前不满足条件的最小的数，贪心的向左或向右即可
? 具体来说可以计算每个数左右各有几个比它大的数，取min后就是该数要移动的步数
?
T3:
? 神仙题
? 首先因为区间只包含不相交，所以区间的关系一定是一个森林，如果再加入一个\([1,n]\)的区间，那么就变成了一棵树
? 考虑有一个显然的dp，设计\(f_{i,j}\)表示以i为根的子树中，重叠了最多j层的最大价值
? 转移：\(f_{u,j}=max(\sum _{v \to son_u} f_{v,j} , \sum _{v \to son_u} f_{v,j-1} + val_u)\)
? 复杂度\(O(n^2)\)，不行
? 分析后会发现，后者大于前者的部分是一个后缀
? 那么原dp数组的转移就相当于后i缀加了一个值，但还是不能做
? 考虑dp数组的差分数组，发现上述变化在差分数组上的体现是按大小插入\(val_u\)
? 那么考虑每个节点只会插入一个值，那么值的总数就是\(O(n)\)级别的
? 每次dp数组相加等价于差分数组相加，用堆或set维护，启发式合并即可
原文：https://www.cnblogs.com/Gkeng/p/11842704.html