矩阵

Posted on Edited on In

题目大意：小凯最近得到了一个数字矩阵。就如他喜欢一个序列的上升子序列一样，他对于上升子矩阵也很感兴趣。上升矩阵是指每行每列都严格上升的矩阵。现在他想要知道，他手里的矩阵有多少个满足条件的子矩阵。

坑

用类似单调栈的东西来维护，本质我也不太明白

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e3 + 66;

int n, m, res;
int a[N][N], up[N], ul[N];

struct S
{
    int w, h;
//constructot
    S (int W = 0, int H = 0) : w(W), h(H) {}
}sta[N];

signed main()
{
    n = read(), m = read();
    for (int i = 1; i <= n; ++ i)
    {
        int cnt = 0, top = 0;
        for (int j = 1; j <= m; ++ j)
        {
            a[i][j] = read();
            ++ up[j], ++ ul[j];
            if (a[i][j] <= a[i - 1][j]) up[j] = 1, ul[j] = 1;
            if (a[i][j] <= a[i][j - 1]) ul[j] = cnt = top = 0;
            S tmp = S(up[j] == ul[j], ul[j]);
            while (top && sta[top].h >= tmp.h)
            {
                tmp.w += sta[top].w;
                cnt -= sta[top].w * sta[top].h;
                -- top;
            }
            sta[++ top] = tmp, cnt += tmp.w * tmp.h;
            if (up[j] > ul[j])
            {
                sta[++ top] = S(1, up[j]);
                cnt += up[j];
            }
            res += cnt;
        }
    }
    put(res);
    return 0;
}