A14307 | Falling Sand (Hard Version)

This is the hard version of the problem. The difference between the versions is the constraints on $a_i$ . You can make hacks only if all versions of the problem are solved.

Little Dormi has recently received a puzzle from his friend and needs your help to solve it.

The puzzle consists of an upright board with $n$ rows and $m$ columns of cells, some empty and some filled with blocks of sand, and $m$ non-negative integers $a_1,a_2,\ldots,a_m$ ( $0 \leq a_i \leq n$ ). In this version of the problem, $a_i$ will always be not greater than the number of blocks of sand in column $i$ .

When a cell filled with a block of sand is disturbed, the block of sand will fall from its cell to the sand counter at the bottom of the column (each column has a sand counter). While a block of sand is falling, other blocks of sand that are adjacent at any point to the falling block of sand will also be disturbed and start to fall. Specifically, a block of sand disturbed at a cell $(i,j)$ will pass through all cells below and including the cell $(i,j)$ within the column, disturbing all adjacent cells along the way. Here, the cells adjacent to a cell $(i,j)$ are defined as $(i-1,j)$ , $(i,j-1)$ , $(i+1,j)$ , and $(i,j+1)$ (if they are within the grid). Note that the newly falling blocks can disturb other blocks.

In one operation you are able to disturb any piece of sand. The puzzle is solved when there are at least $a_i$ blocks of sand counted in the $i$ -th sand counter for each column from $1$ to $m$ .

You are now tasked with finding the minimum amount of operations in order to solve the puzzle. Note that Little Dormi will never give you a puzzle that is impossible to solve.

The first line consists of two space-separated positive integers $n$ and $m$ ( $1 \leq n \cdot m \leq 400\,000$ ).

Each of the next $n$ lines contains $m$ characters, describing each row of the board. If a character on a line is '.', the corresponding cell is empty. If it is '\#', the cell contains a block of sand.

The final line contains $m$ non-negative integers $a_1,a_2,\ldots,a_m$ ( $0 \leq a_i \leq n$ ) — the minimum amount of blocks of sand that needs to fall below the board in each column. In this version of the problem, $a_i$ will always be not greater than the number of blocks of sand in column $i$ .

Print one non-negative integer, the minimum amount of operations needed to solve the puzzle.