Filled Subgrid Count II
You are given a grid of letters. Your task is to calculate, for each letter, the number of rectangular subgrids whose each letter is the same.
$1 \leq n \leq 3000$
$1 \leq \left\lvert \Sigma\right\rvert \leq 26$
Tutorial
My initial idea was to enumerate two bounds, $l$ and $r$, and then count the rectangles where the top is at row $l$ and the bottom is at row $r$. To achieve this, we can use a std::set<std::pair<int, int>> to maintain all segments of the same color. However, this method has a time complexity of $O\left(n^2 \log n\right)$, which is not efficient enough to be accepted. Moreover, we will find out that this method cannot be optimized further.
Let's try another method: treat each position $\left(i, j\right)$ as the lower-right corner of the rectangle, then count the number of such rectangles. To gain some intuition, we can imagine scanning $j$ from left to right.
Let $up_{i, j}$ denote the number of consecutive cells above $\left(i, j\right)$ that have the same color as $\left(i, j\right)$.
We can use $up_{i, j}$ to describe the size of the rectangle more simply: if we fix the bottom of the rectangle at row $i$, the left edge at column $l$, and the right edge at column $r$, then the maximum height is $\min\limits_{l \leq j \leq r} up_{i, j}$.
This gives us some inspiration. We can use a monotonic stack to maintain the minimum values in the array $up_i$. We maintain two pieces of information: the height, and the width over which this height can be extended. Then, we simply multiply these two values and add the result to the final answer.
Code
struct SNOWFLAKE {
SNOWFLAKE(int argc, char* argv[], int TEST_NUMBER) {
int n, m; std::cin >> n >> m;
std::vector<std::string> a(n);
for (auto& i : a) std::cin >> i;
for (auto& i : a) {
for (auto& j : i) j -= 'A';
}
bsl ans(m, 0);
std::vector up(n, bsi(n, 0));
for (int i = 0; i < n; ++i) {
std::vector<pii> stk;
int tar = 0;
for (int j = 0; j < n; ++j) {
if (i > 0 && a[i][j] == a[i - 1][j]) up[i][j] = up[i - 1][j] + 1;
else up[i][j] = 1;
if (j > 0 && a[i][j] != a[i][j - 1]) {
stk.clear();
tar = 0;
}
int len = 1;
while (!stk.empty() && stk.back().first >= up[i][j]) {
tar -= stk.back().first * stk.back().second;
len += stk.back().second;
stk.pop_back();
}
stk.emplace_back(up[i][j], len);
tar += up[i][j] * len;
ans[a[i][j]] += tar;
}
}
for (auto i : ans) std::cout << i << "\n";
}
};