[JOI 2022 Final] 沙堡 2 / Sandcastle 2

Luogu

IDLGP8164

Time4000ms

Memory1096MB

DifficultyP7

2022O2优化JOI（日本）

JOI 君在沙滩上玩耍。他建造了一座沙堡。这座由 JOI 君建造的沙堡位于沙滩上的一个矩形区域内。这个矩形区域有 $H$ 行 $W$ 列。位于从上往下的第 $i$ 行、从左往右的第 $j$ 列的格子的高度为 $A_{i, j}$。**注意所有 $\boldsymbol{A_{i, j}}$ 的值互不相同。** 在沙堡上，JOI 君执行了下列动作。 1. 首先，JOI 君选择一个格子，他从该格子开始移动。 2. 然后，他从当前格子出发朝上下左右四个方向之一移动到相邻的格子上。他必须移动到低于当前格子的格子上。他可以重复此动作零次或更多次。最终，如果我们从上往下看，他经过的格子将形成一个矩形。给定每个格子的高度信息 $A_{i, j}$，写一个程序计算所有可能的由 JOI 君经过的格子组成的矩形的数量。 ## Input 第一行，两个正整数 $H, W$。接下来 $H$ 行，第 $i$ 行 $W$ 个正整数 $A_{i, 1}, A_{i, 2}, \ldots, A_{i, W}$。 ## Output 输出一行，一个数，表示所有可能的由 JOI 君经过的格子组成的矩形的数量。 [samples] ## Note **【样例解释 \#1】** 由于有 $10$ 个可能的由 JOI 君经过的格子组成的矩形，输出 $10$。 ![](https://cdn.luogu.com.cn/upload/image_hosting/ctry6t23.png) 这个样例满足所有子任务的限制。 **【样例解释 \#2】** 由于有 $15$ 个可能的由 JOI 君经过的格子组成的矩形，输出 $15$。 ![](https://cdn.luogu.com.cn/upload/image_hosting/2zaim5fy.png) 这个样例满足子任务 $2, 3, 4, 5$ 的限制。 **【样例解释 \#3】** 举个例子，如下矩形可以由 JOI 君经过的格子组成。由于总共有 $65$ 个可能的矩形，输出 $65$。 ![](https://cdn.luogu.com.cn/upload/image_hosting/q6y9c6d5.png) 这个样例满足子任务 $2, 3, 4, 5$ 的限制。 ---- **【数据范围】** **本题采用捆绑测试。** 对于 $100 \%$ 的数据，$1 \le H, W, H \cdot W \le 5 \times {10}^4$，$1 \le A_{i, j} \le {10}^7$，$A_{i_1, j_1} \ne A_{i_2, j_2}$（$(i_1, j_1) \ne (i_2, j_2)$）。 - 子任务 $1$（$9$ 分）：$H = 1$。 - 子任务 $2$（$10$ 分）：$H \cdot W \le 100$。 - 子任务 $3$（$5$ 分）：$H \cdot W \le 1500$。 - 子任务 $4$（$56$ 分）：$H \cdot W \le 7000$。 - 子任务 $5$（$20$ 分）：无特殊限制。 ---- **译自 [JOI 2022 Final](https://www.ioi-jp.org/joi/2021/2022-ho/index.html) T5「[砂の城 2 ](https://www.ioi-jp.org/joi/2021/2022-ho/2022-ho-t5.pdf) / [Sandcastle 2](https://www.ioi-jp.org/joi/2021/2022-ho/2022-ho-t5-en.pdf)」**

Samples

Input #1

1 5
2 4 7 1 5

Output #1

Input #2

Output #2

Input #3

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

Output #3

API Response (JSON)

{
  "problem": {
    "name": "[JOI 2022 Final] 沙堡 2 / Sandcastle 2",
    "description": {
      "content": "JOI 君在沙滩上玩耍。他建造了一座沙堡。这座由 JOI 君建造的沙堡位于沙滩上的一个矩形区域内。这个矩形区域有 $H$ 行 $W$ 列。位于从上往下的第 $i$ 行、从左往右的第 $j$ 列的格子的高度为 $A_{i, j}$。**注意所有 $\\boldsymbol{A_{i, j}}$ 的值互不相同。** 在沙堡上，JOI 君执行了下列动作。 1. 首先，JOI 君选择一个格子，他从该格子",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 1122304
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8164"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "JOI 君在沙滩上玩耍。他建造了一座沙堡。这座由 JOI 君建造的沙堡位于沙滩上的一个矩形区域内。这个矩形区域有 $H$ 行 $W$ 列。位于从上往下的第 $i$ 行、从左往右的第 $j$ 列的格子的高度为 $A_{i, j}$。**注意所有 $\\boldsymbol{A_{i, j}}$ 的值互不相同。**\n\n在沙堡上，JOI 君执行了下列动作。\n\n1. 首先，JOI 君选择一个格子，他从该格子...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments