CF - Rectangles

Let's first simplify this problem, and then generalize the solution of that problem to this one.

Say we had a matrix of all 0's and 1's. How many submatrices of all 1's are there?

Let's first define a 2D array, $\texttt{longest\_consec}$, that contains the number of consecutive 1's that are directly to the right for each cell (including the cell itself). For example, this matrix...

would have the following $\texttt{longest\_consec}$:

Now, we go through each column and then for each row in reverse, find out for each cell the number of all 1's submatrices where the cell is the upper left corner.

How would we do this?

First, let's initialize a stack $\texttt{rel\_streaks}$ which will have elements with two properties: the value of $\texttt{longest\_consec}$ for that element and the difference in row number (aka distance) between that element and the next element in the stack.

Also initialize a number $\texttt{curr\_sum}$, which, after processing, will contain the number of submatrices of all 1's that start at each cell.

Now, let's say we just started at a particular cell. How should we change our value of $\texttt{curr\_sum}$? Let's not consider the new matrices of one row that just got added first, and just consider the previous arrays. To be able to be extended into the current cell, they need to have a column-wise width less than the current value of $\texttt{longest\_consec}$. To subtract these newly invalid submatrices, we keep on popping the stack while the first part of the first element is larger than the current width and adjusting the value of $\texttt{curr\_sum}$ as needed.

Finally, for each step, we just need to add the current element on to the stack and add to $\texttt{curr\_sum}$ the value of $\texttt{longest\_consec}$ for that cell.

Given that we figured out that simpler problem, we can apply this to the actual problem. Let's make a modified version of $\texttt{longest\_consec}$, where each cell contains the number of consecutive elements to the right with the same value as the current cell.

After that, we run almost the exact same algorithm, only now resetting all the necessary variables when we encounter a number different than the previous ones we were processing.

Time Complexity: $\mathcal{O}(RC)$ for each of $T$ test cases

Copy
#include <algorithm>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::pair;
using std::vector;

int main() {

Copy
import java.io.*;
import java.util.*;

public class Rectangles {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		int testNum = Integer.parseInt(read.readLine());
		for (int t = 0; t < testNum; t++) {
			StringTokenizer initial = new StringTokenizer(read.readLine());
			int rowNum = Integer.parseInt(initial.nextToken());