题目
小明用积木搭了一个城堡。
为了方便，小明在搭的时候用的是一样大小的正方体积本，搭在了一个 nn 行 mm 列的方格图上，每个积木正好占据方格图的一个小方格。
当然，小明的城堡并不是平面的，而是立体的。小明可以将积木垒在别的积木上面。当一个方格上的积木垒得比较高时，就是一个高塔，当一个方格上没有积木时，就是一块平地。
小明的城堡可以用每个方格上垒的积木层数来表示。例如，下面就表示一个城堡。
9 3 3 1
3 3 3 0
0 0 0 0
这个城堡南面和东面都有空地，西北面有一个大房子，在西北角还有一个高塔，东北角有一个车库。
现在，格格巫要来破坏小明的城堡，他施了魔法水淹小明的城堡。
如果水的高度为11，则紧贴地面的那些积木要被水淹，在上面的例子中，有77块积木要被水淹。
如果水的高度为22，则更多积木要被水淹，在上面的例子中，有1313块积木要被水淹。
给定小明的城堡图，请问，水的高度依次为1, 2, 3, ...., H时，有多少块积木要被水淹。
输入
输入的第一行包含两个整数
n, m
。
接下来
n
行，每行
m
个整数，表示小明的城堡中每个位置积木的层数。
接下来包含一个整数
H
，表示水高度的上限。
输出
输出
H
行，每行一个整数。第
i
的整数表示水的高度为
i
时被水淹的积木数量。
样例
输入
3 4
9 3 3 1
3 3 3 0
0 0 0 0
10
输出
7
13
19
20
21
22
23
24
25
25
提示
评测用例规模与约定
对于 40% 的评测用例，1 <= n, m <= 100，1 <= H <= 100，积木层数不超过100；
对于 70% 的评测用例，1 <= n, m <= 1000，1<=H<=1000，积木层数不超过1000；
对于所有评测用例，1 <= n, m <= 1000，1 <= H <= 100000，积木层数不超过10^9
题解
这一题主要的困难是时间复杂度和空间复杂度，如果用二维数组存，会超时，他们无法通过全部测试用例。
我写一下我的解题思路，题目交代了全部的测试用例H<=100000,在这我们可以用数组来存每一个层数的数量，首先定义数组
height[100005]={0}
以样例为例，
9 3 3 1
3 3 3 0
0 0 0 0
则我们的数组是
height[0]=4;
height[1]=1;
height[3]=5;
height[9]=1;
那么
当h=1时，只需要统计h>=1的层数
height[1]+height[3]+height[9]=7;
记录到sum；
当h=2时，只需要统计h>=2的层数
sum+=height[3]+height[9]=6;
直到h
要注意！！
因为层数是不超过10^9，但是会大于100000，所以我们要把所有大于100000的建筑的数量加到
变量b
上，这样我们在每次计算的时候加上
b
就行了。
这样时间复杂度为n^2,不会超市，也不会爆。
代码（c++）
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100007;
int a[maxn];
long long sum[maxn];
int mp[1010][1010];
int main() {
int n, m, h;
cin>>n>>m;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin>>mp[i][j];
cin>>h;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (mp[i][j] > h)
a[h + 1]++;
else
a[mp[i][j]]++;
for (int i = 1; i <= h + 1; i++)
sum[i] = sum[i - 1] + a[i];
long long pre = 0;
for (int i = 1; i <= h; i++) {
cout<<sum[h + 1] - sum[i - 1] + pre<<'\n';
pre = sum[h + 1] - sum[i - 1] + pre;
}
return 0;
}