【NOIP模拟赛】chenzeyu97要请客

2014年10月18日1,6950

题目背景

众所周知,哲♂学家chenzeyu97由于在前面的许多场比赛中都取得了优♂异成绩!所以他在这场赛后要请客!

题目描述

chenzeyu97的家可以看成是一个n*m的矩阵,每块区域都有独一无二的海拔高度h(h>0)!其最大值为n*m。现在他要选择一个子矩阵摆放一张桌子,在他眼里,这样摆放桌子的美观度为这个子矩阵的最小值,他想知道,如果他要求摆放桌子的美观度为i,那么可以选择多少种子矩阵呢?对于所有可能的i值(1<=i<=n*m),你都应该得出其方案数,这样你就能顶替蒟蒻hzwer获得被请客的资格!

输入格式

第一行两个整数n,m

接下来n行,每行m个整数,描述chenzeyu97的家

输出格式

n*m行,每行一个整数,第i行表示美观度i的方案数

样例数据 1

输入

2 3
2 5 1
6 3 4

输出

6
4
5
1
1
1

备注

30%的数据1<=n,m<=50

100%的数据1<=n,m<=300

题解

首先肯定要枚举左右边界L-R吧。。。

我们知道每一行L-R的最小值,这个可以从L-1-R在O1的时间内转移

然后考虑在行上统计答案

问题转换为一个数列,要在On的时间内统计出每个子区间最小值

对于每个数a[x],我们只要知道前一个比它小的数a[y],则a[y+1]到a[x-1]在x之后都不重要了

可以用一个a[x]和f[x]来替代他们,将a[x]和f[x]放入单调栈

具体过程是:如果要加入一个点i,只要栈顶最小值比它大,就不停地把栈顶并给i,同时考虑对答案的影响

类似的,最后处理栈中剩余元素