Gym 101102D---Rectangles(單調棧)

題目鏈接

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.

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.

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

1
3 3
3 3 1
3 3 1
2 2 5

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;
}