区间覆盖(线段树)

X轴上方有若干条平行于X轴的线段，求这些线段能够覆盖X轴的总长度？

输入格式

第一行一个数n(n<=100000)，表示线段个数；

接下来n行，每行两个整数a[i],b[i](-10^8<=a[i],b[i]<=10^8),代表一个线段的两个端点输出覆盖X轴的长度

输入样例

2

10 12

2 4

输出样例

4

 

 

 

1 /* 2 样例： 3 有两段线 4 1 2 5 2 3  6 */ 7  8 #include 
     
       9 using namespace std;10 void print();11 struct node{12     int start,end;13     int cover;14 }segTree[100];15 16 //创建线段树 17 void build(int root,int start,int end){18     segTree[root].start=start;19     segTree[root].end=end;20     segTree[root].cover=0;21     if(start+1
      
       mid){
   //去右子树中找 41             insert(2*root+1,left,right);42         }43         else{
   //如果没有正好合适的，就把区间给拆了 44             insert(2*root,left,mid);45             insert(2*root+1,mid,right);46         } 47     }48 } 49 50 51 int count(int root){52     if(segTree[root].cover==1){53         return segTree[root].end-segTree[root].start;54     }55     //又不等于1，又是叶子节点，肯定给你退出 56     else if(segTree[root].end-segTree[root].start==1){57         return 0;58     }59     else{60         return count(2*root)+count(2*root+1); 61     }62 }63 64 int main(){65     build(1,1,5);66     print();67     insert(1,1,4);68     //insert(1,2,3); 69     print();70     //cout<
       
        <
       
      
     

 

 

再贴一份代码，上面那段代码insert位置有问题

 

1 #include 
     
       2 using namespace std; 3 struct node{ 4     int val; 5     int start; 6     int end; 7 }tree[100]; 8  9 void print();10 11 void build(int root,int start,int end){12     //这里是线段有没有覆盖，所以叶子节点是线段而不是点13     tree[root].start=start;14     tree[root].end=end;15     tree[root].val=0;16     if(start+1