http://www.zybbs.org/JudgeOnline/problem.php?id=1171
4个月以来第一次写BZOJ的题解。。
首先感谢炫教告诉我这题的做法。
这个做法是nLogn的。。。我不知道rank前3的貌似On的做法是怎么做的。。。
如果您知道跪求圣解啊。。。

考虑dp优化的做法。。我们需要支持一个数据结构。。

支持：
(1):插入一个代权线段
(2):询问与一个线段相交的线段中权值最小的线段
(3):删除一个线段(删除的顺序跟插入是一样的)

注意到线段的失效时间是递增的，所以可以用单调队列维护一个线段集合的最小值并支持删除。
使用线段树解决问题，每个节点保存一个单调队列，这个队列保存所有覆盖这个节点并且不覆盖这个点的父亲的线段。
那么插入只要插入到logn个单调队列里面。
同时每个点维护minV表示这个节点的所有子孙的单调队列的最小值的最小值。
那么当一个线段失效的时候。只要对包含这个线段的那logn个节点维护单调队列并更新它们祖先的minV
询问的时候用minV即可。

PS。由于deque内部是用块链实现的，所以初始空间很大，用deque会直接MLE，用list反而就能过。