Algorithmic Engagements 2011 Kangury

听说xyz大爷打算在zjoi讲PA,想想我做过的pa题目一只手都能数过来(现在数了一下刚好5个....)
然后这是在bzoj上有中文题面的,所以我就思(球)考(助)了一(主)下(席)……
然后这题就成了我会做的第5道pa的题目……

其实这题是我去年追随colrko神a题脚步时,看过的一道题,但是去年也没有想到什么好办法……因为感觉很难搞出log级别的做法的样子。
然后最近得到了教诲:

“大胆暴力出奇迹!”
“分块大法好!”

然后主席成功yy出了一个能过的做法。
(后来发现这题其实是@drcrow的去年集训队论文答辩里的例题……论不仔细拜读论文的危害)

对于这种不强制在线的题目,先离线再说。

我们可以考虑把询问区间用一个数据结构保存起来,然后每个询问都有一个属性count。
然后扫一遍袋鼠区间……
当扫到袋鼠[l,r],我们就将询问区间里面和[l,r]有交的询问的count加1,没有交的询问的count赋值为0
然后对于询问i,它对应的count在扫描时达到过的 历史最大值 就是它的最长连续有效子段长。

然后考虑[l,r]与[a,b]有交的条件——
可以看出如果把区间[l,r]看成平面上的点(l,r)的话,那么与[l,r]有交的集合是一个矩形区域。

那么我们需要维护一个平面点集……二维区间赋值和二维区间加以及最后询问历史标记最大值。
历史最大值什么的做过gss2的都明白怎么维护……
然后直接套用kd tree就可以在的时间里面解决这个问题了(kd tree在d维超矩形内查找信息的单次复杂度为)。

不过drcrow提供的思路也比较神……这个大家自行拜读论文吧。。。

Comments

comments powered by Disqus