O(nlogn) C++ Segment Tree


  • 2
    S
    class Solution {
    public:
      int n;
      vector<int> height, lazy;
    
      void push_up(int i) {
        height[i] = max(height[i*2], height[i*2+1]);
      }
    
      void push_down(int i) {
        if (lazy[i]) {
            lazy[i*2] = lazy[i*2+1] = lazy[i];
            height[i*2] = height[i*2+1] = lazy[i];
            lazy[i] = 0;
        }
      }
    
      void update(int i, int l, int r, int L, int R, int val) {
        if (L <= l && r <= R) {
          height[i] = val;
          lazy[i] = val;
          return;
        }
        push_down(i);
        int mid = l + (r-l)/2;
        if (L < mid) update(i*2, l, mid, L, R, val);
        if (R > mid) update(i*2+1, mid, r, L, R, val);
        push_up(i);
      }
    
      int query(int i, int l, int r, int L, int R) {
        if (L <= l && r <= R) return height[i];
        push_down(i);
        int res = 0;;
        int mid = l + (r-l)/2;
        if (L < mid) res = max(res, query(i*2, l, mid, L, R));
        if (R > mid) res = max(res, query(i*2+1, mid, r, L, R));
        return res;
      }
    
      vector<int> fallingSquares(vector<pair<int, int>>& positions) {
        vector<int> a;
        for (auto& p : positions) {
          a.push_back(p.first);
          a.push_back(p.first+p.second);
        }
        sort(a.begin(), a.end());
        n = unique(a.begin(), a.end()) - a.begin();
        a.resize(n);
        
        height.resize(n<<2, 0);
        lazy.resize(n<<2, 0);
        vector<int> res;
        for (auto& p : positions) {
          int l = lower_bound(a.begin(), a.end(), p.first) - a.begin();
          int r = lower_bound(a.begin(), a.end(), p.first+p.second) - a.begin();
          int maxh = query(1, 0, n, l, r);
          update(1, 0, n, l, r, maxh+p.second);
          res.push_back(query(1, 0, n, 0, n));
        }
        return res;
      }
    };
    

  • 0
    W

    Here's a similar idea but with iteration instead of recursion:

    struct Tree {
      Tree(int n) {
        this->n = n;
        t.assign(2*n, 0);
        d.assign(n, 0);
        p.assign(n, false);
      }
    
      int n;
      vector<int> t;
      // Whether there are changes pending to be pushed down at node i.
      vector<bool> p;
      // If p[i] is true, d[i] contains the changes pending to be pushed down at node i.
      vector<int> d;
    
      // Get max between [l, r).
      int get(int l, int r) {
        assert(l < r);
        l += n, r += n;
        push(l);
        push(r - 1);
        int best = INT_MIN;
        for (; l < r; l >>= 1, r >>= 1) {
          if (l&1) best = max(best, t[l++]);
          if (r&1) best = max(t[--r], best);
        }
        return best;
      }
    
      // Set all elements between [l, r) to be X.
      void update(int l, int r, int value) {
        assert(l < r);
        l += n, r += n;
        int l0 = l, r0 = r;
        push(l0);
        push(r0 - 1);
        for (; l < r; l >>= 1, r >>= 1) {
          if (l&1) overwrite(l++, value);
          if (r&1) overwrite(--r, value);
        }
        refresh(l0);
        refresh(r0 - 1);
      }
    
    private:
      // Pushes down all changes from all ancestors of p.
      void push(int u) {
        if (u > 1) push(u >> 1);
        if (u < n and p[u]) {
          overwrite(u << 1, d[u]);
          overwrite(u << 1 | 1, d[u]);
          p[u] = false;
        }
      }
    
      // Updates the given node with the given value.
      void overwrite(int u, int value) {
        t[u] = value;
        if (u < n) {
          p[u] = true;
          d[u] = value;
        }
      }
    
      // Assumes u has changed, so refreshes all of its parents.
      void refresh(int u) {
        for (u >>= 1; u > 0; u >>= 1) {
          if (!p[u]) {
            t[u] = max(t[u << 1], t[u << 1 | 1]);
          }
        }
      }
    };
    
    
    int compress(const vector<int> &x, int value) {
      return lower_bound(x.begin(), x.end(), value) - x.begin();
    }
    
    class Solution {
    public:
        vector<int> fallingSquares(const vector<pair<int, int>>& positions) {
          int n = positions.size();
          vector<int> x;
          for (int i = 0; i < n; ++i) {
            x.push_back(positions[i].first);
            x.push_back(positions[i].first + positions[i].second);
          }
          sort(x.begin(), x.end());
          unique(x.begin(), x.end());
          int m = x.size();
          Tree t(m);
    
          vector<int> ans;
          for (int i = 0; i < n; ++i) {
            int left = positions[i].first;
            int side = positions[i].second;
    
            int l = compress(x, left);
            int r = compress(x, left + side);
    
            int base = t.get(l, r);
            t.update(l, r, base + side);
    
            ans.push_back(t.get(0, m));
          }
          return ans;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.