/* ===== BEGIN IntervalSegmentTree ===== */
struct IntervalSegmentTree {
  unsigned int N = 0;
  vector<int> IntervalCount;
  vector<double> FullLength, CoveredLength;

  IntervalSegmentTree(const vector<double> &Length);

  double get_covered_length() const { return CoveredLength[1]; }

  void _interval_update(int p, int start, int span, int i, int j, int x);  // [i,j[
  void interval_insert(int l, int r) { _interval_update(1,0,N,l,r, 1); }   // [l,r[
  void interval_remove(int l, int r) { _interval_update(1,0,N,l,r,-1); }
};

IntervalSegmentTree::IntervalSegmentTree(const vector<double> &Length) {
  N = 1;
  while (N<Length.size()) N <<= 1;
  IntervalCount.resize(2*N,0);
  FullLength.resize(2*N,0.);
  for (unsigned int p=0; p<Length.size(); ++p) FullLength[N+p] = Length[p];
  for (int p=N-1; p>0; --p) FullLength[p] = FullLength[2*p]+FullLength[2*p+1];
  CoveredLength.resize(2*N,0.);
}

void IntervalSegmentTree::_interval_update(int p, int start, int span, int i, int j, int x) {
  if (start+span<=i || j<=start) return;
  if (i<=start && start+span<=j) IntervalCount[p] += x;
  else {
    _interval_update(2*p,start,span/2,i,j,x);
    _interval_update(2*p+1,start+span/2,span/2,i,j,x);
  }
  if (IntervalCount[p]>0) CoveredLength[p] = FullLength[p];
  else if (p<(int)N) CoveredLength[p] = CoveredLength[2*p]+CoveredLength[2*p+1];
  else CoveredLength[p] = 0.;
}
/* ===== END SegmentTree ===== */