Problem Statement
We are given a totally monotone matrix of size .
For each row, we need to find the column where the minimum value is achieved. More formally, we want to compute where
We are given a totally monotone matrix of size .
For each row, we need to find the column where the minimum value is achieved. More formally, we want to compute where
Solve these external problems (e.g., from Codeforces) to reinforce the lesson material:

A key observation is that the sequence of row minima positions is non-decreasing.
Because of this, one can already apply divide and conquer and solve the problem in . However, there is an even faster algorithm called SMAWK, which solves it in time.
The algorithm is based on two main ideas of Reduce and Interpolate.
In this step, we try to remove columns that definitely cannot contain a row minimum.
The goal is to reduce the number of columns to at most .
We maintain a stack S of columns that have not been eliminated yet. Initially, the stack is empty.
Then we process columns from left to right, one by one.
When we process column j, we do the following:
S is empty, push column j.i = |S|h = S.back()Now compare the values in row i:
then column h can be removed, so we pop it from the stack and repeat.
j is added to the stack if the stack size is still smaller than N.So the code looks like this:
This step removes many unnecessary columns while preserving all possible row minima.


Now we solve the problem recursively only for every second row, for example for all even-indexed rows.

After we know the minima for those rows, we can restore the minima for the remaining rows.
The reason is that the answer is non-decreasing, so for an odd row i we know that:
Therefore, to find f_i, it is enough to do a linear search only in the restricted range from f_{i-1} to f_{i+1}.
This makes the interpolation step efficient.


The full SMAWK algorithm works as follows:
These steps call each other recursively, and the total complexity is:
vector<int> S;
for (int j = 1; j <= m; j++) {
while (!S.empty() && a[S.size()][S.back()] > a[S.size()][j]) {
S.pop_back();
}
if ((int)S.size() < n) {
S.push_back(j);
}
}