![[2017纪中11-3][ARC069-F]高考是不可能高考的 2-sat+线段树优化建图](/uploads/reation/bcimg11.png)
[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的点编号（因为要连另一半嘛），建边时向线段树上节点连，线段树从根往叶子连边，边数
