1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 10 using namespace std; 11 typedef long long int LL; 12 const int INF=2e9+1e8; 13 14 15 16 const int maxn=1e6+10; 17 18 19 struct Date 20 { 21 double l,r,high; 22 int flag; //false 为 下面的边 23 } data[maxn]; 24 double myh[maxn],input[maxn]; 25 int n,k; 26 int getid(double x) 27 { 28 return lower_bound(myh+1,myh+k,x)-myh; 29 } 30 /** 31 * 32 * 线段树 33 * 34 */ 35 struct Seg 36 { 37 int l,r,val; 38 double res; 39 } Tree[maxn]; 40 void build(int i,int l,int r) 41 { 42 Tree[i].l=l,Tree[i].r=r; 43 Tree[i].val=0,Tree[i].res=0; 44 if(l==r) return ; 45 int mid=(l+r)>>1; 46 build(i<<1,l,mid); 47 build(i<<1|1,mid+1,r); 48 } 49 void deal(int i) 50 { 51 if(Tree[i].val) Tree[i].res=myh[Tree[i].r+1]-myh[Tree[i].l]; 52 else if(Tree[i].l==Tree[i].r) Tree[i].res=0.; 53 else Tree[i].res=Tree[i<<1].res+Tree[i<<1|1].res; 54 } 55 void update(int i,int l,int r,int x) // 更新区间,并维护投影长度和, 56 { 57 if(l>r) return ; 58 if(Tree[i].l==l&&Tree[i].r==r) 59 { 60 Tree[i].val+=x; 61 deal(i); 62 return ; 63 } 64 int mid=(Tree[i].l+Tree[i].r)>>1; 65 if(r<=mid) update(i<<1,l,r,x); 66 else if(l>mid) update(i<<1|1,l,r,x); 67 else update(i<<1,l,mid,x),update(i<<1|1,mid+1,r,x); 68 deal(i); 69 } 70 71 double solve() 72 { 73 double ans=0; 74 update(1,getid(data[0].l),getid(data[0].r)-1,1); 75 76 for(int i=1; i<2*n; i++) 77 { 78 ans+=Tree[1].res*(data[i].high-data[i-1].high); 79 update(1,getid(data[i].l),getid(data[i].r)-1,data[i].flag); 80 } 81 return ans; 82 } 83 bool cmp(Date a,Date b) 84 { 85 return a.high