chenzeyu97的家可以看成是一个n*m的矩阵，每块区域都有独一无二的海拔高度h（h>0）！其最大值为n*m。
现在他要选择一个子矩阵摆放一张桌子，在他眼里，这样摆放桌子的美观度为这个子矩阵中所有元素中值的最小值，他想知道，如果他要求摆放桌子的美观度为i，那么可以选择多少种子矩阵呢？
对于所有可能的i值（1≤i≤n*m），你都应该得出其方案数，这样你就能顶替蒟蒻hzwer获得被请客的资格！
题解：http://hzwer.com/4727.html
第1行:两个整数N，M;
接下来N行:每行m个整数，描述一个N*M的矩阵.
30%的数据1≤n,m≤50;
100%的数据1≤n,m≤300.
输出N*M行，每行一个整数，第i行表示美观度i的方案数.
2 3
2 5 1
6 3 4
6
4
5
1
1
1
【样例解释】
美观度为1的情况:
在2*3的矩阵中，分别选择如下的子矩阵:选择第1行第3列、选择第1行第2列~第1行第3列、选择第1行第1列~第1行第3列、选择第1行第3列~第2行第3列、选择第1行第2列~第2行第3列、选择第1行第1列~第2行第3列，其美观度均为1，共6种情况；
美观度为2的情况:
在2*3的矩阵中，分别选择如下的子矩阵:选择第1行第1列、选择第1行第1列~第1行第2列、选择第1行第1列~第2行第1列、选择第1行第1列~第2行第2列，共4种情况。
以此类推…
1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef long long LL;
4 const int MAX = 305;
5 int n, m;
6 int a[MAX][MAX], sta[MAX], top, mn[MAX];
7 LL f[MAX], ans[MAX * MAX];
8
9 int read()
10 {
11 char c;
12 int num, f = 1;
13 while (c = getchar(), !isdigit(c))
14 if (c == ‘-‘)
15 f = -1;
16 num = c - ‘0‘;
17 while (c = getchar(), isdigit(c))
18 num = num * 10 + c - ‘0‘;
19 return f * num;
20 }
21 void calc()
22 {
23 int i, j;//手动写一个单调栈，去模拟将一个点放入后的贡献。
24 LL sum;
25 top = 0;
26 for (i = 1; i <= n; i++)
27 {
28 f[i] = 1;
29 sum = 1;
30 while (top && mn[i] < mn[sta[top]])
31 {
32 ans[mn[sta[top]]] += f[sta[top]] * sum;
33 sum += f[sta[top]];
34 f[i] += f[sta[top]];
35 top--;
36 }
37 sta[++top] = i;
38 }
39 sum = 0;
40 while (top)
41 {
42 ans[mn[sta[top]]] += f[sta[top]] * (sum + 1);
43 sum += f[sta[top]];
44 top--;
45 }
46 }
47 int main()
48 {
49 int i, j, k;
50 n = read();
51 m = read();
52 memset(ans, 0, sizeof(ans));
53 memset(f, 0, sizeof(f));
54 for (i = 1; i <= n; i++)
55 for (j = 1; j <= m; j++)
56 a[i][j] = read();
57 for (i = 1; i <= m; i++)
58 {
59 memset(mn, 127, sizeof(mn));
60 for (j = i; j <= m; j++)
61 {
62 for (k = 1; k <= n; k++)
63 mn[k] = min(mn[k], a[k][j]);//这就是一个简单的预处理，将每一列的每一个区间的最小值都预处理出来
64 calc();
65 }
66 }
67 for (i = 1; i <= n * m; i++)
68 printf("%d\n", ans[i]);
69 return 0;
70 }
[校内自测 NOIP模拟题] chenzeyu97要请客(单调栈)
原文：https://www.cnblogs.com/2529102757ab/p/11832170.html