Description

standard input/output

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 (r1, c1), and the bottom-right cell (r2, c2) (1 ≤ r1 ≤ r2 ≤ R) (1 ≤ c1 ≤ c2 ≤ 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 109, representing the values in the row.

Output

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

Sample Input

Input 
1
3 3
3 3 1
3 3 1
2 2 5
Output 
16

求出由相同数字组成的矩形的个数

一看到这题就想到了这个题：

单调栈优化dp:hdu1506Largest Rectangle in a Histogram &hdu1505city game dp ||附面试题：柱子围水|柱子围面积

原题只是求最大的，对于维护的单调栈每次比较面积即可。而对于这个题，我们维护单调栈的值依旧是列序号。我们设ans[i][j]表示以(i,j)为右下角点的可组成矩阵个数,假设在(i,j)左边离它最近的高度比它小的位置是(i,p)那么ans[i][j]=ans[i][k]+(j-k)*h[i][j]。但是如果(i,j)和(i,k)不是同一种图案就不能加进去啦

#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int a[1005][1005],ans[1005][1005],h[1005][1005];
int s[1005],pos[1005];
int main()
{
  //  freopen("cin.txt","r",stdin);
    int t,r,c;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&r,&c);
        memset(h,0,sizeof(h));
        memset(ans,0,sizeof(ans));
        memset(a,0,sizeof(a));
        for(int i=1;i<=r;i++)
        {
            for(int j=1;j<=c;j++)
            {
                scanf("%d",&a[i][j]);
                if(a[i-1][j]!=a[i][j])h[i][j]=1;
                else h[i][j]=h[i-1][j]+1;
            }
        }
        //for(int i=1;i<=r;i++){for(int j=1;j<=c;j++)printf("%d ",h[i][j]);puts(""); }
        int num;
        long long sum=0;
        for(int i=1;i<=r;i++)
        {
            for(int j=1;j<=c;j++)
            {
                if(a[i][j-1]!=a[i][j])
                {
                    num=1;
                    s[1]=j-1;//
                    h[i][j-1]=0;//
                    s[++num]=j;
                    //pos[j]=j-1;//
                    ans[i][j]=h[i][j];//
                    sum+=(long long)ans[i][j];
                }
                else
                {
                    while(h[i][j]<=h[i][s[num]])num--;
                    int p=s[num];
                    s[++num]=j;
                    ans[i][j]+=h[i][j]*(j-p);
                    if(h[i][p]!=0)ans[i][j]+=ans[i][p];
                    sum+=ans[i][j]*1LL;
                }
            }
        }
        printf("%I64d\n",sum);
    }
    return 0;
}