树套树笔记

没错这是个大坑

这两天看到一鬼畜题,带插入区间k小值,BZOJ3065,网上搜的hzwer写法貌似是替罪羊树套线段树(?!!)省队里面一神犇也大致给我讲了讲,说实话,并没有怎么听懂Orz

总之先从最基础的树套树开始,也就是带修改区间k小值

静态的区间k小值大家都会做,内存换时间就划分树,时间换内存就主席树

带修改区间k小值呢,其实思路和主席树差不多(主席树:要是我能查询[a,b)区间里进入左子树的数的个数就好了!),要是我能查询[a,b)区间里进入左子树的数的个数就好了。但是带修改怎么查呢?

假设对于一个区间,有数组flag_inleft,其中flag_inleft[i]==1表示元素i进入左子树,==0表示进入右子树,那么对于区间[a,b),我们只要求sum {i | a<=i<b }的值就能达到目的了。

好了,那么我们在每个区间里面放一颗树状数组或者线段树…就能logn的时间查询上诉sansum值了,每次查询时间(应该是不紧却的)上界是O(log^2(n)),(因为树高logn,每个节点查询又需要logn(感觉这里不紧却))。还是很好写的。

(我会回来填坑的)

(我回来填坑了)

其实这题用Splay也可以写的嘛,主席树套Splay。

众所周知Splay是可以维护区间的,鉴于查询区间k大的时候我们只需要主席树的每一个节点支持查询“到i的时候有多少个数进入了左边”,而Splay又支持快速的插入和查询前缀和…后面就不用详细展开了。

更加抽象一点,对于序列上的一个区间k小类型的操作f,执行这个操作的复杂度为O(f*logn)。因为在主席树上一共要经过logn那么多个点,而每个点都要花O(f)维护。

例如主席树,查询(二分)是logn的,所以主席树整体查询复杂度是O(logn*logn)。

例如划分树,查询(二分)是1的,所以划分树整体查询复杂度是O(1*logn)。

例如带修改的主席树(主席树套树状数组),修改操作(在树状数组上)是logn的,所以整体修改复杂度是O(logn*logn)

DP单调队列优化笔记

不敢说完全理解了吧Orz但至少大致知道总体思路了

对于方程形如f(i)=min/max{f(j)+g(i)}, h(i)<=j<i, 其中g(i)的值只与i有关, 且对于a<b<c, h(a)<h(b)<h(c), 换句话说, h(x)单调(不一定严格)递增, 可以使用单调队列优化,下面假定目标是最小化

维护储存”可取用子问题”(也就是所有j的可能取值)的单调队列q, 使得其中f的值单调递增, 对于需要计算的状态f(i), 弹出q头部元素直到q.front.location>=h(i),(很好理解吧),此时f(i)的最优值即为q.front.value+g(i); 然后弹出q尾部元素直到q.back.value<f(i),然后再把f(i)压入队列尾部. 为什么呢? 1. 因为队列是单调的, 所以队头的元素的值肯定为最小化的子问题,而且没有遗漏,因为2.如果一个子状态k被遗漏了,则f(k)<f(t),(t为用这种方法计算出的最优子问题),而且h(i)<=k,但这是不可能的,因为从队头只弹出了h(i)(!<=)k的子状态,所以f(k)必然还在q中;又因为对q的操作保证了队列里子状态f值的单调,所以k必然在t之前,因此获取到的最优子问题应该为k,这和题设矛盾;综上所诉,t为最优的子状态.

一篇好论文:用单调性优化动态规划  1D1D动态规划优化初步

一些基础题:生产产品, 玩具装箱, 烽火传递, Cut the sequence

(肯定还要回来填坑的…表情)