[2017纪中11-3][ARC069-F]高考是不可能高考的 2-sat+线段树优化建图
题面 原题 首先考虑二分答案k,验证就可以用2-sat。假如要选某一个x[i],那么x[i]左右距离k的区间内的点都不能选,于是这些点都必须选另一半;y[i]同理。 由于边数太多,直接建图是不可接受的,考虑到不能选的点都在一个区间内,于是把所有x[i],y[i]排序,开一棵线段树,x的位置存y的点编号,y的位置存x的点编号(因为要连另一半嘛),建边时向线段树上节点连,线段树从根往叶子连边,边数