BZOJ 大sz的游戏

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反而就能过。

6 thoughts on “BZOJ 大sz的游戏

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>