问题理解

我们有 n 条南北向河流（位于 x = 1, 2, …, n）和 m 条东西向河流（位于 y = 1, 2, …, m）。
它们的交点 (x, y) 就是一座城市，总城市数为 n × m。

• 如果一条河流是干净的（+），那么位于这条河流上的城市可以直接取水，成本为 0。
• 如果一条河流是污染的（-），那么位于这条河流上的城市需要从最近的干净河流运水，成本是 到最近干净河流的曼哈顿距离。

关键观察

1. 成本为 0 的城市
   一个城市 (i, j) 的成本为 0，当且仅当 南北向河流 i 干净 或 东西向河流 j 干净（或两者都干净）。
   设：

   • A = 干净的南北向河流数量
   • B = 干净的东西向河流数量

   则成本为 0 的城市数量为： [ A \times m + B \times n - A \times B ] 因为：

   • 所有在干净南北向河流上的城市：A × m
   • 所有在干净东西向河流上的城市：B × n
   • 两者都干净的城市被重复计算了一次，减去 A × B。

2. 成本不为 0 的城市
   如果城市 (i, j) 所在的南北向河流和东西向河流都污染，那么它需要运水。
   它的成本 = min( 到最近干净南北向河流的距离 , 到最近干净东西向河流的距离 )。

   因为南北向河流在 x 轴上，东西向河流在 y 轴上，所以：

   • 到最近干净南北向河流的距离 = min(|i - u|)，其中 u 是干净南北向河流的 x 坐标。
   • 到最近干净东西向河流的距离 = min(|j - v|)，其中 v 是干净东西向河流的 y 坐标。

   成本 = min( min_u |i-u|, min_v |j-v| )。

3. 成本分布
   所有成本不为 0 的城市，它们的成本值只取决于南北向河流的干净位置集合和东西向河流的干净位置集合。
   当某条河流状态改变时，会影响到整行或整列的城市成本。

问题转化

我们需要支持：

• 动态更新某条河流的干净/污染状态
• 给定预算 c，求最多能供水的城市数

策略：

1. 先统计成本为 0 的城市数（它们肯定能供水）。
2. 剩下的城市（成本不为 0）按成本从小到大排序，用预算 c 尽量覆盖。

数据结构与算法思路

维护干净河流位置

用两个平衡树（set）分别存：

• 干净南北向河流的 x 坐标
• 干净东西向河流的 y 坐标

这样可以在 O(log n) 时间内找到某个位置最近的干净河流（前驱/后继）。

维护成本分布

难点在于：当一条河流状态变化时，会影响很多城市的成本。
直接枚举所有城市更新成本显然不可行（n, m 可达 1e5）。

观察：

• 对于南北向河流，如果它变干净，那么整行城市成本变为 0；如果它变污染，那么这一行城市的成本需要重新计算（取决于该行到其他干净南北向河流的距离，以及该行到干净东西向河流的距离）。
• 但是整行整列的成本变化有规律：对于所有 (i, j)，如果 i 和 j 都污染，那么成本 = min( distX(i), distY(j) )，其中 distX(i) 是 i 到最近干净南北向河流的距离，distY(j) 是 j 到最近干净东西向河流的距离。

因此，我们可以：

• 对每个 i（南北向河流），如果它污染，则 distX[i] = min(i - 前一个干净南北向河流, 后一个干净南北向河流 - i)，如果一边没有干净河流则取无穷大。
• 对每个 j（东西向河流），如果它污染，则 distY[j] 同理。
• 那么所有成本不为 0 的城市 (i, j) 的成本 = min(distX[i], distY[j])。

这样，我们只需要维护 distX 和 distY 数组，当河流状态变化时，更新受影响的 distX 或 distY 值。

查询处理

给定预算 c：

1. 计算成本为 0 的城市数 zero_count。
2. 剩下的城市（成本不为 0）数量 = (n - A) × (m - B)。
3. 我们需要知道这些城市中，成本 ≤ t 的城市数，使得总成本 ≤ c。

这可以通过二分成本阈值 t 来实现：

• 对于每个可能的成本值 t，统计有多少对 (i, j) 满足：
  • i 是污染的南北向河流
  • j 是污染的东西向河流
  • min(distX[i], distY[j]) ≤ t
• 这等于： [ \sum_{i \in \text{polluted X}} \sum_{j \in \text{polluted Y}} [\min(distX[i], distY[j]) \le t] ] 可以拆成：
  • 所有 distX[i] ≤ t 的 i 对应的 j 数量（全部满足）
  • 所有 distX[i] > t 的 i 对应的 j 中，distY[j] ≤ t 的数量

即： [ \text{count} = \text{cntXLeqT} \times (m-B) + \text{cntXGtT} \times \text{cntYLeqT} ] 其中：

• cntXLeqT = 污染南北向河流中 distX[i] ≤ t 的数量
• cntXGtT = 污染南北向河流中 distX[i] > t 的数量 = (n - A) - cntXLeqT
• cntYLeqT = 污染东西向河流中 distY[j] ≤ t 的数量

总成本可以用类似方法计算（按 t 分组求和），然后判断是否 ≤ c。

复杂度

• 每次更新河流状态：O(log n) 更新平衡树，O(1) 更新 distX/distY 的计数结构。
• 每次查询：O(log(max(n, m))) 二分 t，O(1) 计算 count 和 cost。

总结

这道题的核心是将二维城市成本问题，通过 min(distX[i], distY[j]) 分解成两个一维问题，并利用平衡树维护最近干净河流距离，再用计数结构快速统计满足成本阈值的城市数量和总成本，从而在 O(log n) 级别完成每次操作。