← 返回题目列表

Codeforces · 1534/F2

F2. 落沙(困难版)

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

这是问题的困难版本。版本之间的差异在于 $$$a_i$$$ 的约束。只有当问题的所有版本都得到解决后,你才能进行黑客攻击。

小多米最近从他的朋友那里收到了一个谜题,需要你的帮助来解决它。

拼图由一个直立板组成,其中包含 $$$n$$$ 行和 $$$m$$$ 列单元格,其中一些是空的,一些填充有沙块,以及 $$$m$$$ 非负整数 $$$a_1,a_2,\ldots,a_m$$$ ($$$0 \leq a_i \leq n$$$)。在此版本的问题中,$$$a_i$$$ 始终不大于 $$$i$$$ 列中沙块的数量。

当一个装满沙子的单元格受到干扰时,沙子块将从其单元格掉落到柱子底部的沙子计数器上(每个柱子都有一个沙子计数器)。当一块沙子下落时,与下落的沙块任何一点相邻的其他沙块也会受到干扰并开始下落。具体来说,在单元格 $$$(i,j)$$$ 处受到扰动的一块沙子将穿过下面的所有单元格,包括列内的单元格 $$$(i,j)$$$,从而扰动沿途的所有相邻单元格。这里,与单元$$$(i,j)$$$相邻的单元被定义为$$$(i-1,j)$$$、$$$(i,j-1)$$$、$$$(i+1,j)$$$和$$$(i,j+1)$$$(如果它们在网格内)。请注意,新落下的方块可能会干扰其他方块。

在一次操作中,您可以扰动任何一块沙子。当从 $$$1$$$ 到 $$$m$$$ 的每一列的第 $$$i$$$ 沙子计数器中至少有 $$$a_i$$$ 沙子块时,谜题就解决了。

现在,您的任务是找到解决难题所需的最少操作量。请注意,小多米永远不会给你一个无法解决的难题。

输入

第一行由两个空格分隔的正整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n \cdot m \leq 400\,000$$$) 组成。

接下来的 $$$n$$$ 行包含 $$$m$$$ 个字符,描述棋盘的每一行。如果一行中的字符为“.”,则相应的单元格为空。如果是“#”,则单元格中包含一块沙子。

最后一行包含 $$$m$$$ 非负整数 $$$a_1,a_2,\ldots,a_m$$$ ($$$0 \leq a_i \leq n$$$) — 每列中需要落到棋盘下方的最小沙块数量。在此版本的问题中,$$$a_i$$$ 始终不大于 $$$i$$$ 列中沙块的数量。

输出

打印一个非负整数,即解决该难题所需的最少运算量。

示例

输入 #1

5 7
#....#.
.#.#...
#....#.
#....##
#.#....
4 1 1 1 0 3 1

输出 #1

3

输入 #2

3 3
#.#
#..
##.
3 1 1

输出 #2

1

输入 #3

7 5
.#..#
#....
..##.
..##.
..###
..#..
#.##.
0 0 2 4 2

输出 #3

1

注意

例如$$$1$$$,通过扰动从左起第一行和左起第六列的沙块,以及从上数第二行和左起第四列的沙块,可以让每列中落下所有所需数量的沙子。可以证明,少于 $$$3$$$ 操作是不可能的,因此答案是 $$$3$$$。这是第一个示例中的谜题。

例如$$$2$$$,通过干扰顶行和最右列的单元格,可以导致棋盘中的所有沙块落入底部的柜台中。因此,答案是$$$1$$$。这是第二个例子中的谜题。

例如$$$3$$$,通过干扰顶行和最右列的单元格,可以使每列中落下所有所需数量的沙子。可以证明,少于 $$$1$$$ 操作是不可能的,因此答案是 $$$1$$$。这是第三个例子中的谜题。