序：

模拟赛考了一道 2-sat 问题。之前从来没听过……

考完才发现其实这个东东只要一个小小的 tarjan 求强连通分量就搞定了。

这个方法真是巧妙啊，拿来讲讲。

What is it？ [・_・？]

这个算法是为了应对一些这样的条件：x1 与 x1 中至少有一个成立

算法：

既然是“2"-sat，那就要充分发挥 “two” 的优势，由于x1限制关系，有一些点我们选了后，有一些点就不能选了，那我们就只能选另一个点了满足 x2。

我们把 a 想它必须选的点 b 连有向边，这样就构成了一个图，判定的话，判断是否有两个不能同时存在的点在一个强连通分量中就好了！

这有一位大佬写的比我更好

当然重点是讲模拟赛的题！

例题  Flags：

题目大意：数轴上有 n 个旗子，第 i 个可以插在坐标 xi 或者 yi，最大化两两旗子之间的最小距离。

题解：

我们可以二分答案，转化为一个 2-sat 问题。

二分最小距离 d，那么一个点 a 向左向右 d 的 b 点都不能选，那么选了 a 就必须选 b 的另一个位置，然后我们连边，最后判断是不是有一个点的两个位置是不是在一个强连通分量里，在则不能，否则可以。

这题还有一个点就是如果直接建边的话，就有 $n^2$ 条边，你会发现这题一个点的连边都是连续的，那就不妨线段树优化建图。具体思想。

CODE：

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 using namespace std;  7    8 int v[100005];  9 int n,x,y,tot=0,h[100005]; 10 int scc[100005],dfn[100005],low[100005],C,cnt; 11 bool vis[100005]; 12 struct Edge{ 13     int x,next; 14 }e[5000000]; 15 pair
           
             a[20005]; 16 stack
            
              s; 17 18 inline void add_edge(int x,int y){ 19 e[++tot].x=y; 20 e[tot].next=h[x],h[x]=tot; 21 } 22 23 void tarjan(int x){ 24 dfn[x]=low[x]=++cnt; 25 s.push(x),vis[x]=true; 26 for(int i=h[x];~i;i=e[i].next){ 27 if(!dfn[e[i].x]){ 28 tarjan(e[i].x),low[x]=min(low[x],low[e[i].x]); 29 }else if(vis[e[i].x]){ 30 low[x]=min(low[x],dfn[e[i].x]); 31 } 32 } 33 if(dfn[x]==low[x]){ 34 C++; 35 int tmp; 36 for(;;){ 37 tmp=s.top(); 38 vis[tmp]=false,scc[tmp]=C; 39 s.pop(); 40 if(tmp==x)break; 41 } 42 } 43 } 44 45 void build(int o,int l,int r){ 46 if(r-l==1){ 47 add_edge(o+n*2,a[l].second^1); 48 return; 49 } 50 add_edge(o+n*2,(o<<1)+n*2); 51 add_edge(o+n*2,(o<<1|1)+n*2); 52 int mid=l+r>>1; 53 build(o<<1,l,mid),build(o<<1|1,mid,r); 54 } 55 56 void link(int o,int l,int r,int x,int y,int a){ 57 if(l>=x&&r<=y){ 58 add_edge(a,o+n*2); 59 return; 60 } 61 int mid=l+r>>1; 62 if(x
             
              <<1,l,mid,x,y,a); 63 if(y>mid)link(o<<1|1,mid,r,x,y,a); 64 } 65 66 inline pair
              
                get(int x,int len){ 67 int l=0,r=x; 68 pair
               
                 ans; 69 while(l
                
                 >1; 71 if(a[x].first-a[mid].first
                 
                  >1; 78 if(a[mid].first-a[x].first
                  
                    x=get(i,d); 94 if(i
                   
                    >1;115 if(check(mid))l=mid;116 else r=mid-1;117 }118 printf("%d",l);119 }