[Hnoi2010]Planar 2

额。。上次那个裸判是M^2的。。数据太弱这样都能过大囧。。。
构造性的数据很容易出囧。。。没办法只好再研究一下了瀑布汗。。
考虑这个问题。。实际上就是一个区间图的2-染色问题,
那么首先吧问题分成两部分。。
首先是给每个节点染色,
其次是判断这个样的染色可不可行。。
第一个问题如果不能是M^2的话。。我们需要对某条边,
快速的找出一个与它相交的边把它染掉,同时把它在可选边中删掉。。
不难发现用线段树可以在LogN的时间搞定。。
第二个问题分别考虑2个颜色好了。。
需要判断一堆边中有没有相交的。。怎么搞都行囧。。

One thought on “[Hnoi2010]Planar 2

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>