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.
For example $$$1$$$, by disturbing both blocks of sand on the first row from the top at the first and sixth columns from the left, and the block of sand on the second row from the top and the fourth column from the left, it is possible to have all the required amounts of sand fall in each column. It can be proved that this is not possible with fewer than $$$3$$$ operations, and as such the answer is $$$3$$$. Here is the puzzle from the first example.   For example $$$2$$$, by disturbing the cell on the top row and rightmost column, one can cause all of the blocks of sand in the board to fall into the counters at the bottom. Thus, the answer is $$$1$$$. Here is the puzzle from the second example.   For example $$$3$$$, by disturbing the cell on the top row and rightmost column, it is possible to have all the required amounts of sand fall in each column. It can be proved that this is not possible with fewer than $$$1$$$ operation, and as such the answer is $$$1$$$. Here is the puzzle from the third example.   
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.
import itertools
import math
from math import inf

def readline():
    return map(int, input().split())

def blocks(bits):
    start = None
    for (i, bit) in enumerate(itertools.chain(bits, [False])):
        if bit and start is None:
            start = i
        if not bit and start is not None:
            yield (start, i)
            start = None

def test_blocks():
    assert list(blocks([0, 0, 0])) == []
    assert list(blocks([0, 1, 1])) == [(1, 3)]
    assert list(blocks([1, 1])) == [(0, 2)]
    assert list(blocks([0, 1, 1, 0, 0, 1, 1, 0])) == [(1, 3), (5, 7)]

def cut(iterable):
    for (a, b, __) in iterable:
        yield (a, b)

def magic_blocks(blocks, prev_blocks, annotate_w=False):
    if annotate_w:
        blocks = ((a, b, b - a) for (a, b) in blocks)
    glue = itertools.chain(prev_blocks, [(inf, inf)])
    (gb, ge) = (-inf, -inf)
    (ma, mb, weight) = (None, None, 0)
    for (a, b, w) in itertools.chain(blocks, [(inf, inf, inf)]):
        if ma is None:
            (ma, mb, weight) = (a, b, w)
            continue
        while ge <= a and ge < inf:
            (gb, ge) = next(glue)
        if gb < mb:
            mb = b
            weight += w
        else:
            yield (ma, mb, weight)
            (ma, mb, weight) = (a, b, w)

def test_magic_blocks():
    blocks = ((0, 2), (4, 7), (10, 15))

    def tcut(mb):
        return tuple(cut(mb))
    assert tcut(magic_blocks(blocks, [])) == blocks
    assert tcut(magic_blocks(blocks, [(2, 4)])) == blocks
    assert tcut(magic_blocks(blocks, [(1, 4)])) == blocks
    assert tcut(magic_blocks(blocks, [(1, 5)])) == ((0, 7), (10, 15))
    assert tcut(magic_blocks(blocks, [(1, 10)])) == ((0, 7), (10, 15))
    assert tcut(magic_blocks(blocks, [(1, 11)])) == ((0, 15),)
    assert tcut(magic_blocks(blocks, [(1, 2), (3, 4), (7, 10)])) == blocks
    assert tcut(magic_blocks(blocks, [(1, 2), (3, 4), (6, 100)])) == ((0, 2), (4, 15))
    assert tcut(magic_blocks(blocks, [(7, 100), (101, 104)])) == blocks
    assert tcut(magic_blocks((), [(7, 100), (101, 104)])) == ()
unset = object()

def debug(*args):
    import sys
    print(*args, file=sys.stderr)

def solve_1(seq, a):
    ans = 0
    t = False
    for (is_sand, ai) in zip(seq, a):
        if not is_sand:
            t = False
        if ai:
            assert is_sand
            if not t:
                ans += 1
                t = True
    print(ans)

def main():
    (n, m) = readline()
    s = [[ch == '#' for ch in input()] for __ in range(n)]
    a = list(readline())
    ans = 0
    if n == 1:
        solve_1(s[0], a)
        return
    m_blocks = [()]
    for i in range(m):
        sb = blocks((row[i] for row in reversed(s)))
        m_blocks.append(tuple(magic_blocks(sb, cut(m_blocks[-1]), annotate_w=True)))
    m_blocks.pop(0)
    m_blocks.append(())
    for i in range(m, 0, -1):
        m_blocks[i - 1] = tuple(magic_blocks(m_blocks[i - 1], cut(m_blocks[i])))
    c = None
    f = -1
    for i in range(m):
        sand = a[i]
        next_c = unset
        next_f = -1
        top = -1
        for (from_, to, weight) in m_blocks[i]:
            top = to - 1
            if from_ <= f:
                next_f = top
            sand -= weight
            if sand > 0:
                continue
            if c is not None and c > top:
                continue
            if next_c is unset:
                next_c = from_
        assert sand <= 0
        if next_c is not unset and (c is not None or (a[i] and next_c > f)):
            if c is None:
                ans += 1
            c = next_c
            f = top
        else:
            c = None
            f = next_f
    print(ans)
if __name__ == '__main__':
    main()
import itertools, math
from math import inf

def readline():
    return map(int, input().split())

def blocks(bits):
    start = None
    for (i, bit) in enumerate(itertools.chain(bits, [False])):
        if bit and start is None:
            start = i
        if not bit and start is not None:
            yield (start, i)
            start = None

def test_blocks():
    assert list(blocks([0, 0, 0])) == []
    assert list(blocks([0, 1, 1])) == [(1, 3)]
    assert list(blocks([1, 1])) == [(0, 2)]
    assert list(blocks([0, 1, 1, 0, 0, 1, 1, 0])) == [(1, 3), (5, 7)]

def cut(iterable):
    for (a, b, __) in iterable:
        yield (a, b)

def magic_blocks(blocks, prev_blocks, annotate_w=False):
    if annotate_w:
        blocks = ((a, b, b - a) for (a, b) in blocks)
    glue = itertools.chain(prev_blocks, [(inf, inf)])
    (gb, ge) = (-inf, -inf)
    (ma, mb, weight) = (None, None, 0)
    for (a, b, w) in itertools.chain(blocks, [(inf, inf, inf)]):
        if ma is None:
            (ma, mb, weight) = (a, b, w)
            continue
        while ge <= a and ge < inf:
            (gb, ge) = next(glue)
        if gb < mb:
            mb = b
            weight += w
        else:
            yield (ma, mb, weight)
            (ma, mb, weight) = (a, b, w)

def test_magic_blocks():
    blocks = ((0, 2), (4, 7), (10, 15))

    def tcut(mb):
        return tuple(cut(mb))
    assert tcut(magic_blocks(blocks, [])) == blocks
    assert tcut(magic_blocks(blocks, [(2, 4)])) == blocks
    assert tcut(magic_blocks(blocks, [(1, 4)])) == blocks
    assert tcut(magic_blocks(blocks, [(1, 5)])) == ((0, 7), (10, 15))
    assert tcut(magic_blocks(blocks, [(1, 10)])) == ((0, 7), (10, 15))
    assert tcut(magic_blocks(blocks, [(1, 11)])) == ((0, 15),)
    assert tcut(magic_blocks(blocks, [(1, 2), (3, 4), (7, 10)])) == blocks
    assert tcut(magic_blocks(blocks, [(1, 2), (3, 4), (6, 100)])) == ((0, 2), (4, 15))
    assert tcut(magic_blocks(blocks, [(7, 100), (101, 104)])) == blocks
    assert tcut(magic_blocks((), [(7, 100), (101, 104)])) == ()
unset = object()

def debug(*args):
    import sys
    print(*args, file=sys.stderr)

def solve_1(seq, a):
    ans = 0
    t = False
    for (is_sand, ai) in zip(seq, a):
        if not is_sand:
            t = False
        if ai:
            assert is_sand
            if not t:
                ans += 1
                t = True
    print(ans)

def main():
    (n, m) = readline()
    s = [[ch == '#' for ch in input()] for __ in range(n)]
    a = list(readline())
    ans = 0
    if n == 1:
        solve_1(s[0], a)
        return
    m_blocks = [()]
    for i in range(m):
        sb = blocks((row[i] for row in reversed(s)))
        m_blocks.append(tuple(magic_blocks(sb, cut(m_blocks[-1]), annotate_w=True)))
    m_blocks.pop(0)
    m_blocks.append(())
    for i in range(m, 0, -1):
        m_blocks[i - 1] = tuple(magic_blocks(m_blocks[i - 1], cut(m_blocks[i])))
    c = None
    f = -1
    for i in range(m):
        sand = a[i]
        next_c = unset
        next_f = -1
        top = -1
        for (from_, to, weight) in m_blocks[i]:
            top = to - 1
            if from_ <= f:
                next_f = top
            sand -= weight
            if sand > 0:
                continue
            if c is not None and c > top:
                continue
            if next_c is unset:
                next_c = from_
        assert sand <= 0
        if next_c is not unset and (c is not None or (a[i] and next_c > f)):
            if c is None:
                ans += 1
            c = next_c
            f = top
        else:
            c = None
            f = next_f
    print(ans)
if __name__ == '__main__':
    main()
import itertools, math
from math import inf

def readline():
    return map(int, input().split())

def blocks(bits):
    start = None
    for (i, bit) in enumerate(itertools.chain(bits, [False])):
        if bit and start is None:
            start = i
        if not bit and start is not None:
            yield (start, i)
            start = None

def test_blocks():
    assert list(blocks([0, 0, 0])) == []
    assert list(blocks([0, 1, 1])) == [(1, 3)]
    assert list(blocks([1, 1])) == [(0, 2)]
    assert list(blocks([0, 1, 1, 0, 0, 1, 1, 0])) == [(1, 3), (5, 7)]

def cut(iterable):
    for (a, b, __) in iterable:
        yield (a, b)

def magic_blocks(blocks, prev_blocks, annotate_w=False):
    if annotate_w:
        blocks = ((a, b, b - a) for (a, b) in blocks)
    glue = itertools.chain(prev_blocks, [(inf, inf)])
    (gb, ge) = (-inf, -inf)
    (ma, mb, weight) = (None, None, 0)
    for (a, b, w) in itertools.chain(blocks, [(inf, inf, inf)]):
        if ma is None:
            (ma, mb, weight) = (a, b, w)
            continue
        while ge <= a and ge < inf:
            (gb, ge) = next(glue)
        if gb < mb:
            mb = b
            weight += w
        else:
            yield (ma, mb, weight)
            (ma, mb, weight) = (a, b, w)

def test_magic_blocks():
    blocks = ((0, 2), (4, 7), (10, 15))

    def tcut(mb):
        return tuple(cut(mb))
    assert tcut(magic_blocks(blocks, [])) == blocks
    assert tcut(magic_blocks(blocks, [(2, 4)])) == blocks
    assert tcut(magic_blocks(blocks, [(1, 4)])) == blocks
    assert tcut(magic_blocks(blocks, [(1, 5)])) == ((0, 7), (10, 15))
    assert tcut(magic_blocks(blocks, [(1, 10)])) == ((0, 7), (10, 15))
    assert tcut(magic_blocks(blocks, [(1, 11)])) == ((0, 15),)
    assert tcut(magic_blocks(blocks, [(1, 2), (3, 4), (7, 10)])) == blocks
    assert tcut(magic_blocks(blocks, [(1, 2), (3, 4), (6, 100)])) == ((0, 2), (4, 15))
    assert tcut(magic_blocks(blocks, [(7, 100), (101, 104)])) == blocks
    assert tcut(magic_blocks((), [(7, 100), (101, 104)])) == ()
unset = object()

def debug(*args):
    import sys
    print(*args, file=sys.stderr)

def solve_1(seq, a):
    ans = 0
    t = False
    for (is_sand, ai) in zip(seq, a):
        if not is_sand:
            t = False
        if ai:
            assert is_sand
            if not t:
                ans += 1
                t = True
    print(ans)

def main():
    (n, m) = readline()
    s = [[ch == '#' for ch in input()] for __ in range(n)]
    a = list(readline())
    ans = 0
    if n == 1:
        solve_1(s[0], a)
        return
    m_blocks = [()]
    for i in range(m):
        sb = blocks((row[i] for row in reversed(s)))
        m_blocks.append(tuple(magic_blocks(sb, cut(m_blocks[-1]), annotate_w=True)))
    m_blocks.pop(0)
    m_blocks.append(())
    for i in range(m, 0, -1):
        m_blocks[i - 1] = tuple(magic_blocks(m_blocks[i - 1], cut(m_blocks[i])))
    c = None
    f = -1
    for i in range(m):
        sand = a[i]
        next_c = unset
        next_f = -1
        top = -1
        for (from_, to, weight) in m_blocks[i]:
            top = to - 1
            if from_ <= f:
                next_f = top
            sand -= weight
            if sand > 0:
                continue
            if c is not None and c > top:
                continue
            if next_c is unset:
                next_c = from_
        assert sand <= 0
        if next_c is not unset and (c is not None or (a[i] and next_c > f)):
            if c is None:
                ans += 1
            c = next_c
            f = top
        else:
            c = None
            f = next_f
    print(ans)
if __name__ == '__main__':
    main()