almost 3 years ago

前言

扫描线神题一道,膜现场ACzpl大神。

题目大意

中文题你还不看题。。。

分析

首先我们考虑第二问。如果只考虑一个方向的话,假设是向上,有向边表示会挡住,那么抽象出来的图是一个DAG(脑补一下很显然的。。。),因此无论往哪个方向走都是有解的。
然后就是连边的问题,暴力连边是的,显然会TLE+MLE,我们考虑减少边的数量:
(贴一张课件里的图。。。)


因此这样建边就是的了,具体操作方法就是离散化后一根扫描线从左往右扫,因为两条线段之间的大小关系并不会变化,因此我们用一棵平衡树维护即可。。。(偷懒用set
这样对于第二问直接输出拓扑序即可,现在考虑第一问。
我们倒过来把删除变成插入,对四个方向分别判断(其实上和下,左和右可以一起判断),依旧以向上为例子,判断这条线段的区间内是否有拓扑序在其前面的点即可,如果有必定矛盾。这个用一棵线段树维护就可以了。
因此时间复杂度就是,只是常数比较大就是了。。。
bzoj2584.cpp

← QTREE系列 bzoj3153:AAA树 →
 
comments powered by Disqus