线段树五 李超线段树

李超线段树,又是一个神奇的线段树
模板题大意: 对区间等差数列取max(min)
题目翻译: 对一个平面直角坐标系,我对于区间插入很多条直线(线段),然后询问当在某个点时y的最大值
维护这个区间内的所有直线中,从上往下能够看到的最长的那个线段,也就是没有被其他直线覆盖长度最大的段。 -> 可以点
首先我们可以考虑用一个标记把当前覆盖的直线存下来
首先对于一个没有被覆盖过的区间我们之间覆盖就好
然后我们考虑如果当前操作的这个区间是被修改过的
李超线段树
如果发现这两个直线在这个区间内并不相交,就直接把这个区间内的标记处理一下,
如果这个两个线段相交【如图一】红色的线段是最初存在的(虽说在处理的时候不重要)
当我们新加入绿色的线段我们就直接for一下,这样就很轻易的处理完了这部分,但这样很容易被卡成O(n^2)
所以我们就考虑到了线段树
首先我们对这样的区间我们就可以把这堆东西分成两部分,[l, 交点], (交点,r],然后首先我们可以直接分成这两部分,然后我们可以随便选取一段区间比如说我们选取[l, 交点]这个然后我们把绿色的部分(的标记)向下递归【如图二】,然后很发现区间(交点,r]中的绿色部分的线段就不会对任何答案产生贡献所以就直接不管了(其实还是要用红色的线段去更新一下标记),这样我们就可以将新加入的这部分线段的贡献保留在这个区间内部,
【图二】和【图三】是上面这步操作的两种不同的选择结果
我们就很容易发现我们要是选择【图三】的明显时间复杂度会很舒服,要是选择图二则很容易退化到O(n^2)
所以对于【图四】的选择我肯定会优先于选择【图三】(发现图四没有被提到,所以我就加了这句话,不想改这个图了)
所以很容易得到下边的结论【来自于lxl大佬的】

那我们肯定考虑pushdown小的那一段
可以发现每次pushdown的时候标记长度会/2
每次pushdown的复杂度是O( logn ),每个标记会pushdown O( logn )次
所以复杂度为O( mlog^2n )

然后对于查询来说,因为在线段树上的单点查询,肯定是每次都会经过所有包含这个点的log个结点(区间)所以只需要在访问的时候取一下max就好

点赞
  1. YingLi说道:

    Fatal error: Uncaught ArgumentCountError: Too few arguments to function Walker_Comment::filter_comment_text(), 1 passed in /www/admin/www.lzx1999.cn_80/wwwroot/wordpress/wp-includes/class-wp-hook.php on line 287 and exactly 2 expected in /www/admin/www.lzx1999.cn_80/wwwroot/wordpress/wp-includes/class-walker-comment.php:267 Stack trace: #0 /www/admin/www.lzx1999.cn_80/wwwroot/wordpress/wp-includes/class-wp-hook.php(287): Walker_Comment->filter_comment_text('<p>TQL %%%%</p>...') #1 /www/admin/www.lzx1999.cn_80/wwwroot/wordpress/wp-includes/plugin.php(206): WP_Hook->apply_filters('<p>TQL %%%%</p>...', Array) #2 /www/admin/www.lzx1999.cn_80/wwwroot/wordpress/wp-content/themes/kratos-pjax-master/inc/ua.php(432): apply_filters('comment_text', 'TQL %%%%') #3 /www/admin/www.lzx1999.cn_80/wwwroot/wordpress/wp-content/themes/kratos-pjax-master/inc/ua.php(436): user_agent_display_comment() #4 /www/admin/www.lzx1999.cn_80/wwwroot/wordpress/wp-includes/class-wp-hook.php(289): user_agent('TQL %%%%') #5 /www/admin/www.lzx1999.cn_80/www in /www/admin/www.lzx1999.cn_80/wwwroot/wordpress/wp-includes/class-walker-comment.php on line 267