← 返回题目列表

AtCoder · joi2022ho_e

E. 沙堡 2

中文机器翻译题面 查看原题

配点: 100 点

JOI 你在海滩上玩耍并建造了沙堡。 JOI 您建造的城堡位于一个带有沙滩的矩形区域内。这个矩形区域是垂直的 H 行,横 W 表示为分为列的网格,垂直方向平行于南北方向,水平方向平行于东西方向。从北方 i 行目 (1 \leqq i \leqq H),从西边 正方形 j 列目 (1 \leqq j \leqq W的高度是 A_{i, j} 。但是,A_{i, j} 的值都不同。

JOI 对这座沙堡执行了以下操作。

  1. 选择一个方格并从该方格上方开始。
  2. 之后,北、南、东、西相邻降低要移动到一个正方形上, 重复至少0 次。

最后,JOI 如果你从上面看一下你访问过的广场的面积,这是 1 由两个矩形表示。

每个方块的高度 给定信息 A_{i, j} ,编写一个程序来查找 JOI 访问的正方形中可能存在的矩形区域的数量。


入力

输入是按以下格式从标准输入给出的。所有输入值都是整数。

H W
A_{1, 1} A_{1, 2} \cdots A_{1, W}
A_{2, 1} A_{2, 2} \cdots A_{2, W}
\vdots
A_{H, 1} A_{H, 2} \cdots A_{H, W}

出力

标准输出显示 JOI 访问的正方形有多少个可能的矩形区域。1 行。


制約

  • H \geqq 1.
  • W \geqq 1.
  • H \times W \leqq 50\,000.
  • 1 \leqq A_{i, j} \leqq 10\,000\,000 (1 \leqq i \leqq H,1 \leqq j \leqq W).
  • A_{i_1, j_1} \neq A_{i_2, j_2} (1 \leqq i_1 \leqq H,1 \leqq j_1 \leqq W,1 \leqq i_2 \leqq H,1 \leqq j_2 \leqq W,(i_1, j_1) \neq (i_2, j_2)).

小課題

  1. (9 点) H = 1.
  2. (10 点) H \times W \leqq 100.
  3. (5 点) H \times W \leqq 1\,500.
  4. (56 点) H \times W \leqq 7\,000.
  5. (20 点)没有额外的限制。

入力例 1

1 5
2 4 7 1 5

出力例 1

10

JOI 以下是您访问过的广场的矩形区域。 10 既然有一条可能的街道,10 。 您将获得


入力例 2

3 2
18 10
19 12
17 13

出力例 2

15

JOI 以下是您访问过的广场的矩形区域。 15 既然有一条可能的街道,15 。 您将获得

此输入示例是一个小作业。 2, 3, 4, 5 满足约束。


入力例 3

3 5
83 47 36 38 40
13 10 26 68 67
15 19 20 70 90

出力例 3

65

例如,考虑以下矩形区域。包括其他一切在内,总计 65 因为有65 。 您将获得

此输入示例是一个小作业。 2, 3, 4, 5 满足约束。