Shooting (Hard)

**This is the hard version of the problem. The only difference between this and easy version is the constraints on $N$ — notably, in this version, $N \leq 3 \cdot 10^5$.\ This problem is worth $90$ points in division $2$ and $100$ points in division $1$** Aarsi and Krypto were competing in a shooting game. You are given a matrix $A$ of size $N \times M$ representing a shooting board. The cell