SHARE
TWEET

Untitled

a guest Nov 8th, 2019 89 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /* ===== BEGIN IntervalSegmentTree ===== */
  2. struct IntervalSegmentTree {
  3.   unsigned int N = 0;
  4.   vector<int> IntervalCount;
  5.   vector<double> FullLength, CoveredLength;
  6.  
  7.   IntervalSegmentTree(const vector<double> &Length);
  8.  
  9.   double get_covered_length() const { return CoveredLength[1]; }
  10.  
  11.   void _interval_update(int p, int start, int span, int i, int j, int x);  // [i,j[
  12.   void interval_insert(int l, int r) { _interval_update(1,0,N,l,r, 1); }   // [l,r[
  13.   void interval_remove(int l, int r) { _interval_update(1,0,N,l,r,-1); }
  14. };
  15.  
  16. IntervalSegmentTree::IntervalSegmentTree(const vector<double> &Length) {
  17.   N = 1;
  18.   while (N<Length.size()) N <<= 1;
  19.   IntervalCount.resize(2*N,0);
  20.   FullLength.resize(2*N,0.);
  21.   for (unsigned int p=0; p<Length.size(); ++p) FullLength[N+p] = Length[p];
  22.   for (int p=N-1; p>0; --p) FullLength[p] = FullLength[2*p]+FullLength[2*p+1];
  23.   CoveredLength.resize(2*N,0.);
  24. }
  25.  
  26. void IntervalSegmentTree::_interval_update(int p, int start, int span, int i, int j, int x) {
  27.   if (start+span<=i || j<=start) return;
  28.   if (i<=start && start+span<=j) IntervalCount[p] += x;
  29.   else {
  30.     _interval_update(2*p,start,span/2,i,j,x);
  31.     _interval_update(2*p+1,start+span/2,span/2,i,j,x);
  32.   }
  33.   if (IntervalCount[p]>0) CoveredLength[p] = FullLength[p];
  34.   else if (p<(int)N) CoveredLength[p] = CoveredLength[2*p]+CoveredLength[2*p+1];
  35.   else CoveredLength[p] = 0.;
  36. }
  37. /* ===== END SegmentTree ===== */
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top