1439: Diagonal Fancy
[命题人 : ]
题目描述
Given a matrix $A$ with $n$ rows and $m$ columns, your objective is to compute the total number of continuous sub-square matrices $B$ that are [b]diagonal fancy[/b].
A square matrix $B$ is designated as diagonal fancy if it satisfies the subsequent criteria:
Here, $B_{i,j}$ signifies the element located at the $i$-th row and $j$-th column of matrix $B$.
A continuous sub-square matrix from matrix $A$ with $n$ rows and $n$ columns is defined as the matrix derived from $A$ by selecting continuous $n$ rows and continuous $n$ columns.
A square matrix $B$ is designated as diagonal fancy if it satisfies the subsequent criteria:
- For any indices $i_1$, $j_1$, $i_2$, and $j_2$, if $i_1 - j_1 = i_2 - j_2$, then $B_{i_1,j_1} = B_{i_2,j_2}$.
- For any indices $i_1$, $j_1$, $i_2$, and $j_2$, if $i_1 - j_1 \neq i_2 - j_2$, then $B_{i_1,j_1} \neq B_{i_2,j_2}$.
Here, $B_{i,j}$ signifies the element located at the $i$-th row and $j$-th column of matrix $B$.
A continuous sub-square matrix from matrix $A$ with $n$ rows and $n$ columns is defined as the matrix derived from $A$ by selecting continuous $n$ rows and continuous $n$ columns.
输入
Ensure to use cin/cout and disable synchronization with stdio to avoid unexpected TLE verdict.
The input consists of multiple test cases. The first line of the input contains an integer $T$ ($1 \leq T \leq 100$), which represents the number of test cases.
The first line of each test case contains two integers $n$ and $m$ ($1 \leq n, m \leq 1000$), representing the number of rows and columns in the matrix $A$.
Each of the next $n$ lines contains $m$ space-separated integers $A_{i,1}, A_{i,2}, \ldots, A_{i,m}$ ($1 \leq A_{i,j} \leq n \times m$), representing the elements of the matrix $A$ for that particular test case.
It is guaranteed that $\sum n\times m\le 10^7$ over all test cases.
The input consists of multiple test cases. The first line of the input contains an integer $T$ ($1 \leq T \leq 100$), which represents the number of test cases.
The first line of each test case contains two integers $n$ and $m$ ($1 \leq n, m \leq 1000$), representing the number of rows and columns in the matrix $A$.
Each of the next $n$ lines contains $m$ space-separated integers $A_{i,1}, A_{i,2}, \ldots, A_{i,m}$ ($1 \leq A_{i,j} \leq n \times m$), representing the elements of the matrix $A$ for that particular test case.
It is guaranteed that $\sum n\times m\le 10^7$ over all test cases.
输出
For each test case, output a single integer in a single line, which represents the count of continuous sub-square matrices in matrix $A$ that are diagonal fancy.
样例输入 Copy
3
2 2
1 2
3 1
2 2
1 2
2 1
3 3
1 2 3
4 1 2
5 4 1
样例输出 Copy
5
4
14
提示
In the first test case, there are $5$ diagonal fancy subsquares in total. They are listed in bold below.
$$
\begin{align}
&\textbf{1}\text{ }2&\ \ \ \ &1\text{ }\textbf{2}&\ \ \ \ &1\text{ }2&\ \ \ \ &1\text{ }2&\ \ \ \ &\textbf{1}\text{ }\textbf{2}&\notag\newline
&3\text{ }1&\ \ \ \ &3\text{ }1&\ \ \ \ &\textbf{3}\text{ }1&\ \ \ \ &3\text{ }\textbf{1}&\ \ \ \ &\textbf{3}\text{ }\textbf{1}&\notag
\end{align}
$$
$$
\begin{align}
&\textbf{1}\text{ }2&\ \ \ \ &1\text{ }\textbf{2}&\ \ \ \ &1\text{ }2&\ \ \ \ &1\text{ }2&\ \ \ \ &\textbf{1}\text{ }\textbf{2}&\notag\newline
&3\text{ }1&\ \ \ \ &3\text{ }1&\ \ \ \ &\textbf{3}\text{ }1&\ \ \ \ &3\text{ }\textbf{1}&\ \ \ \ &\textbf{3}\text{ }\textbf{1}&\notag
\end{align}
$$