Gym - 101102D Rectangles （单调栈）

Given an R×C grid with each cell containing an integer, find the number of subrectangles in this grid that contain only one distinct integer; this means every cell in a subrectangle contains the same integer.

A subrectangle is defined by two cells: the top left cell (r₁, c₁), and the bottom-right cell (r₂, c₂) (1 ≤ r₁ ≤ r₂ ≤ R) (1 ≤ c₁ ≤ c₂ ≤ C), assuming that rows are numbered from top to bottom and columns are numbered from left to right.

Input

The first line of input contains a single integer T, the number of test cases.

The first line of each test case contains two integers R and C (1 ≤ R, C ≤ 1000), the number of rows and the number of columns of the grid, respectively.

Each of the next R lines contains C integers between 1 and 10⁹, representing the values in the row.

Output

For each test case, print the answer on a single line.

Example

Input

Output

16

题意:问由单一数字组成的矩阵的个数。
思路：
dp[i][j]表示以位置i,j为右下角的矩阵个数。
先处理出当前位置向上延伸相同的数字最高有多高。用num[i]记录。
用单调栈处理出在此之前的，第一个小于自己的num[i].
判断中间有没有插入别的数，再进行处理。详见solve函数。

 #include<iostream>

 #include<algorithm>

 #include<vector>

 #include<stack>

 #include<queue>

 #include<map>

 #include<set>

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<ctime>

 #define fuck(x) cout<<#x<<" = "<<x<<endl;

 #define debug(a,i) cout<<#a<<"["<<i<<"] = "<<a[i]<<endl;

 #define ls (t<<1)

 #define rs ((t<<1)|1)

 using namespace std;

 typedef long long ll;

 typedef unsigned long long ull;

 const int maxn = ;

 const int maxm = ;

 const int inf = 2.1e9;

 const ll Inf = ;

 const int mod = ;

 const double eps = 1e-;

 const double pi = acos(-);

 int n,m;

 int mp[maxn][maxn];

 int num[maxn];

 ll ans;

 struct  node{

     int num,pos;

 };

 stack<node>st;

 int pre[maxn];

 int pre1[maxn];

 ll dp[maxn];

 void solve(int t){

     memset(dp,,sizeof(dp));

     memset(pre,,sizeof(pre));

     while(!st.empty()){

         st.pop();

     }

     num[]=-;

     for(int i=m;i>=;i--){

         while(!st.empty()&&st.top().num>num[i]){

             pre[st.top().pos]=i;

             st.pop();

         }

         st.push(node{num[i],i});

     }

     int k=;

     for(int i=;i<=m;i++){

         if(mp[t][i]!=mp[t][i-]){

             k=i;

         }

         pre1[i]=k;

     }

     int pree;

     for(int i=;i<=m;i++){

         if(pre1[i]>pre[i]){

             dp[i]=1ll*num[i]*(i-pre1[i]+);

             ans+=dp[i];

         }

         else{

             dp[i]=1ll*num[i]*(i-pre[i])+dp[pre[i]];

             ans+=dp[i];

         }

     }

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     while(T--){

         scanf("%d%d",&n,&m);

         for(int i=;i<=n;i++){

             for(int j=;j<=m;j++){

                 scanf("%d",&mp[i][j]);

             }

         }

         ans=;

         memset(num,,sizeof(num));

         for(int i=;i<=n;i++){

             for(int j=;j<=m;j++){

                 if(mp[i][j]==mp[i-][j]){

                     num[j]++;

                 }

                 else{

                     num[j]=;

                 }

             }

             solve(i);

         }

         printf("%lld\n",ans);

     }

     return ;

 }

巴特西

Gym - 101102D Rectangles （单调栈）

最新文章

热门文章