![[AT2336] Flags（二分答案+2-SAT+线段树优化建图）](/uploads/reation/bcimg5.png)
[AT2336] Flags（二分答案+2-SAT+线段树优化建图）
首先看出可以二分出距离，然后2-SAT判断是否可行。但建图时需要枚举每组节点，复杂度O(n²)，且最多n*(n-1)/2条边，空间也开不下。如果现将2*n个位置排序，那么对于排序后第i个点，和它距离小于一个值的点分别在它左边和右边的两个连续区间内，于是可以线段树优化建图。建树时首先将每个节点向其父亲连边，代表子区间内的点一定在更大的区间里。然后枚举点，二分求出和 i 距离小于一个值的区间的端点...
