Gym 101102D---Rectangles(单调栈)

2018-06-17 23:43:15来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

题目链接

http://codeforces.com/gym/101102/problem/D

 

problem  description

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.

Example
input
1
3 3
3 3 1
3 3 1
2 2 5
output
16

 

题意:输入R C表示一个矩阵,里面每一个矩阵元素中有一个数在1~1e9之间 ,求有多少个子矩阵里面的所有数相同?

思路:先对每一列从上到下遍历,记录h[i][j]表示从当前元素往上最多有多少数相同, 然后对每一行遍历,记录ans[i][j] 表示以a[i][j]为右下角的元素的子矩阵个数,那么可以发现: 设当前元素之前同一行中小于它且最近的元素为a[i][k] 那么ans[i][j]=ans[i][k]+(j-k)*h[i][j] 为了降低复杂度可以在当前行从左向右遍历的过程中把各列的高放入单调栈中,这样可以快速知道小于当前元素最近的元素的位置,最后对ans[][]求和就是结果 ;

 

代码如下:

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <set>
#include <queue>
#include <vector>
using namespace std;
int a[1005][1005];
int h[1005][1005];
int ans[1005][1005];///包含某一点的贡献值;
int S[1005],pos[1005];///单调栈;

int main()
{
    int T;
    cin>>T;
    int R,C;
    while(T--)
    {
        scanf("%d%d",&R,&C);
        memset(h,0,sizeof(h));
        memset(a,0,sizeof(a));
        memset(ans,0,sizeof(ans));
        for(int i=1;i<=R;i++)
            for(int j=1;j<=C;j++)
            scanf("%d",&a[i][j]);
        for(int j=1;j<=C;j++)
        {
            int s;
            for(int i=1;i<=R;i++)
            {
                if(a[i][j]==a[i-1][j]) s++;
                else s=1;
                h[i][j]=s;
            }
        }
        long long sum=0;
        for(int i=1;i<=R;i++)
        {
            int num;
            for(int j=1;j<=C;j++)
            {
                if(a[i][j]!=a[i][j-1]){
                    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];
                    continue;
                }
                while(h[i][j]<=h[i][S[num]]) num--;
                pos[j]=S[num];
                S[++num]=j;
                ans[i][j]+=h[i][j]*(j-pos[j]);
                if(h[i][pos[j]]!=0)
                ans[i][j]+=ans[i][pos[j]];
                sum+=(long long)ans[i][j];
            }
        }
        printf("%lld\n",sum);
    }
    return 0;
}

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:HDU 1028(母函数)

下一篇:nyoj-一笔画问题-欧拉图+联通判定