🐰🐱 兔猫信奥学院：加菲老师的“冰霜阵”调查

题目描述

冬日来临，加菲老师在兔猫信奥学院的庭院里布置了一块神秘的冰霜阵。阵列由一个 \(m\times n\) 的整数矩阵 grid 构成，阵法规则是：

• 每一行，从左到右的数值按非严格递减排列（也就是每个元素不大于前一个元素）。
• 每一列，从上到下的数值也按非严格递减排列。

当阵法遭遇寒流，所有负数的位置就会结成冰晶。加菲老师请小兔和小猫统计整个矩阵中冰晶（负数）的数量，以便部署更多的防护魔法。

请你设计两种算法并实现：

1. 二分查找法，时间复杂度约为 \(O(m\log n)\) 或 \(O(n\log m)\)。
2. 线性扫描法，时间复杂度为 \(O(m + n)\)。

输入格式

m n
grid[0][0] grid[0][1] … grid[0][n-1]
grid[1][0] grid[1][1] … grid[1][n-1]
…
grid[m-1][0] grid[m-1][1] … grid[m-1][n-1]

• 第一行包含两个整数 \(m, n\)，表示矩阵的行数和列数。
• 接下来 \(m\) 行，每行 \(n\) 个整数，表示矩阵中的元素。
  数据范围： 1<=n,m<=6000

输出格式

count

• 输出一个整数 count，表示矩阵中小于 0 的元素（冰晶）的总个数。

样例输入 1

4 4
4  3  2 -1
3  2  1 -1
1  1 -1 -2
-1 -1 -2 -3

样例输出 1

8

样例输入 2

2 2
3 2
1 0

样例输出 2

0