BZOJ 3166 [Heoi2013]Alo

发布于 2017-07-08  166 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3166

题意:定义一个区间的价值为区间内元素次大值异或区间中任意一个元素的最大值,求整个序列所有区间价值的最大值


求区间最大异或值是一个经典问题... 可以看 这篇  的一部分

问题的核心在于怎么处理次大值的限制,对于一个确定的次大值 x,可以包含它的合法极大区间有两种:最大在左边和最大在右边。实际上我们在处理的时候直接取这两个区间的并即可

然后怎么搞呢... 按照权值由大到小排序,这样保证后插入的肯定比新插入的小,一个合法的区间可以表示为 [x 的前驱的前驱+1,x 的后继的后继-1]...

前驱后继什么的... 我写了个 treap,结果并没有 set 块 T.T,还被暴力碾了....

 


一个非常弱的准退役OIER