main.cpp

// Source: https://leetcode.com/problems/subrectangle-queries
// Title: Subrectangle Queries
// Difficulty: Medium
// Author: Mu Yang <http://muyang.pro>

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Implement the class `SubrectangleQueries` which receives a `rows x cols` rectangle as a matrix of integers in the constructor and supports two methods:
//
// 1.`updateSubrectangle(int row1, int col1, int row2, int col2, int newValue)`
// - Updates all values with `newValue` in the subrectangle whose upper left coordinate is `(row1,col1)` and bottom right coordinate is `(row2,col2)`.
//
// 2.`getValue(int row, int col)`
// - Returns the current value of the coordinate `(row,col)` fromthe rectangle.
//
// **Example 1:**
//
// ```
// Input:
// ["SubrectangleQueries","getValue","updateSubrectangle","getValue","getValue","updateSubrectangle","getValue","getValue"]
// [[[[1,2,1],[4,3,4],[3,2,1],[1,1,1]]],[0,2],[0,0,3,2,5],[0,2],[3,1],[3,0,3,2,10],[3,1],[0,2]]
//
// Output:
// [null,1,null,5,5,null,10,5]
//
// Explanation:
// SubrectangleQueries subrectangleQueries = new SubrectangleQueries([[1,2,1],[4,3,4],[3,2,1],[1,1,1]]);
// // The initial rectangle (4x3) looks like:
// // 1 2 1
// // 4 3 4
// // 3 2 1
// // 1 1 1
// subrectangleQueries.getValue(0, 2); // return 1
// subrectangleQueries.updateSubrectangle(0, 0, 3, 2, 5);
// // After this update the rectangle looks like:
// // 5 5 5
// // 5 5 5
// // 5 5 5
// // 5 5 5
// subrectangleQueries.getValue(0, 2); // return 5
// subrectangleQueries.getValue(3, 1); // return 5
// subrectangleQueries.updateSubrectangle(3, 0, 3, 2, 10);
// // After this update the rectangle looks like:
// // 5   5   5
// // 5   5   5
// // 5   5   5
// // 10  10  10
// subrectangleQueries.getValue(3, 1); // return 10
// subrectangleQueries.getValue(0, 2); // return 5
// ```
//
// **Example 2:**
//
// ```
// Input:
// ["SubrectangleQueries","getValue","updateSubrectangle","getValue","getValue","updateSubrectangle","getValue"]
// [[[[1,1,1],[2,2,2],[3,3,3]]],[0,0],[0,0,2,2,100],[0,0],[2,2],[1,1,2,2,20],[2,2]]
//
// Output:
// [null,1,null,100,100,null,20]
//
// Explanation:
// SubrectangleQueries subrectangleQueries = new SubrectangleQueries([[1,1,1],[2,2,2],[3,3,3]]);
// subrectangleQueries.getValue(0, 0); // return 1
// subrectangleQueries.updateSubrectangle(0, 0, 2, 2, 100);
// subrectangleQueries.getValue(0, 0); // return 100
// subrectangleQueries.getValue(2, 2); // return 100
// subrectangleQueries.updateSubrectangle(1, 1, 2, 2, 20);
// subrectangleQueries.getValue(2, 2); // return 20
// ```
//
// **Constraints:**
//
// - There will be at most `500`operations considering both methods:`updateSubrectangle` and `getValue`.
// - `1 <= rows, cols <= 100`
// - `rows ==rectangle.length`
// - `cols == rectangle[i].length`
// - `0 <= row1 <= row2 < rows`
// - `0 <= col1 <= col2 < cols`
// - `1 <= newValue, rectangle[i][j] <= 10^9`
// - `0 <= row < rows`
// - `0 <= col < cols`
//
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

#include <vector>

using namespace std;

// Brute-Force
class SubrectangleQueries {
  vector<vector<int>>& rectangle;

 public:
  SubrectangleQueries(vector<vector<int>>& rectangle) : rectangle(rectangle) {}

  void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {
    for (int r = row1; r <= row2; ++r) {
      for (int c = col1; c <= col2; ++c) {
        rectangle[r][c] = newValue;
      }
    }
  }

  int getValue(int row, int col) const {  //
    return rectangle[row][col];
  }
};

// Lazy Update
//
// Since there are at most 500 operations,
// we can store the update as logs, and linear scan it during get.
class SubrectangleQueries2 {
  struct Update {
    int row1, col1, row2, col2;
    int newValue;
  };

  const vector<vector<int>>& rectangle;
  vector<Update> updates;

 public:
  SubrectangleQueries2(const vector<vector<int>>& rectangle) : rectangle(rectangle) {}

  void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {  //
    updates.emplace_back(row1, col1, row2, col2, newValue);
  }

  int getValue(int row, int col) const {
    int n = updates.size();
    for (int i = n - 1; i >= 0; --i) {
      int row1 = updates[i].row1;
      int col1 = updates[i].col1;
      int row2 = updates[i].row2;
      int col2 = updates[i].col2;
      if (row1 <= row && row <= row2 && col1 <= col && col <= col2) {
        return updates[i].newValue;
      }
    }

    return rectangle[row][col];
  }
};

// Hierarchy
//
// Use hierarchical boxes with different sizes:
// 1x1, 1x2, 2x2, 2x1, 1x4, 2x4, 4x4, 4x2, 4x1, 1x8, ...
//
// On update, find the largest boxes that forms the update range,
// and set those boxes to the new value.
// We also track the update time for each box.
//
// On query, find all the boxes covering this cell,
// and returns the value of the latest updated box.
class SubrectangleQueries3 {
 public:
  SubrectangleQueries3(vector<vector<int>>& rectangle) {
    // TODO:
  }

  // O(logR * logC)
  void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {
    // TODO:
  }

  // O(logR * logC)
  int getValue(int row, int col) const {
    return 0;  // TODO:
  }
};