1 /*  2 题意：给你n条垂直线段，问有多少组三个线段，两两可见，  3 可见定义为对于两条线段有一条水平线段连接，不经过任意其他线段；  4   5 线段树建图，然后爆力判有几组（不知道效率如何）；  6 从左到右扫描，先判断该区间内有可以连接哪几条线段，建图；  7 然后再插入；  8   9 问题：对于[1,4],[1,2],[3,4],[1,4] 10 如果直接1-2,3-4覆盖，当用1-4query的时候， 11 会发现不存在(2,3)区域的标记， 12 解决方法，每个点之间都插入一个点，用偶数表示原先的点， 13 用奇数表示点之间的区域，0,1,2,3,4    14                     0   1   2 15                          16 */ 17 #include
     
       18 #include
      
        19 #include
       
         20 #include
        
          21 #include
         
           22 #include
          
            23 #include
           
             24 #define lson l,m,rt<<1 25 #define rson m+1,r,rt<<1|1 26 using namespace std; 27 const int N=8000+10; 28 struct Edge{ 29 int l,r,idx; 30 Edge(){} 31 Edge(int a,int b,int c):l(a),r(b),idx(c){} 32 void output(){ 33 cout<
            
             <<" "<
             
              <<" "<
              
               <
               
                 g[N]; 37 vector
                
                  mz[N]; 38 bool vis[N][N]; 39 int n; 40 int col[N<<3];//要扩大 41 void pushdown(int rt){ 42 if (col[rt]!=-1){ 43 col[rt<<1]=col[rt<<1|1]=col[rt]; 44 col[rt]=-1; 45 } 46 } 47 void pushup(int rt){ 48 if (col[rt<<1]!=col[rt<<1|1]){ 49 col[rt]=-1; 50 }else col[rt]=col[rt<<1]; 51 } 52 void update(int L,int R,int v,int l,int r,int rt){ 53 if (L<=l && r<=R){ 54 col[rt]=v; 55 return; 56 } 57 pushdown(rt); 58 int m=(l+r)>>1; 59 if (L<=m) update(L,R,v,lson); 60 if (m< R) update(L,R,v,rson); 61 pushup(rt); 62 63 } 64 void query(int L,int R,int v,int l,int r,int rt){ 65 66 if (L<=l && r<=R && col[rt]!=-1){ 67 if (col[rt]==0) return ; 68 if (vis[v][col[rt]]==0){ 69 mz[v].push_back(col[rt]); 70 mz[col[rt]].push_back(v); 71 vis[v][col[rt]]=1; 72 vis[col[rt]][v]=1; 73 } 74 return ; 75 } 76 if (l==r) return; 77 pushdown(rt); 78 int m=(l+r)>>1; 79 if (L<=m) query(L,R,v,lson); 80 if (m< R) query(L,R,v,rson); 81 } 82 void work(){ 83 memset(col,0,sizeof(col)); 84 for (int i=0;i<=n;i++) for (int j=0;j<=n;j++) vis[i][j]=0; 85 for (int i=0;i