P12920 [POI 2021/2022 R3] 河流 / Rzeki

翻译来自于 [LibreOJ](https://loj.ac/p/4857)。

**题目译自 [XXIX Olimpiada Informatyczna – III etap](https://sio2.mimuw.edu.pl/c/oi29-3/dashboard/) [Rzeki](https://szkopul.edu.pl/problemset/problem/KxrjYJ-gIqnT7k6iL3aF-g3t/statement/)** > 等到最后一条河被污染，等到最后一棵树被砍掉，等到最后一条鱼被捕捉，然后我们才明白，原来钞票是不能吃的。——印第安谚语 在字节王国，有 $n$ 条河流从南向北沿着直线 $x=i$ $(i=1,2,\ldots,n)$ 流动，还有 $m$ 条河流从西向东沿着直线 $y=j$ $(j=1,2,\ldots,m)$ 流动。每两条河流的交点处都有一座城市。每座城市中，一条河流通过隧道流过，不与另一条混合。过去，每座城市都从其所在的河流取水。然而如今，一些河流污染严重，已无法净化水质，城市不得不从其他河流运水。运水成本等于城市到河流直线的距离。运水使用的是沿河流分布的双向公路，重卡可以通行（河流流向不影响运水）。 遗憾的是，字节王国的预算有限，可能无法为所有城市供水。更复杂的是，有些河流会被净化，有些又会重新污染。 请你编写一个程序，读取河流的当前状态，并支持两种操作：更改河流状态，以及回答在给定预算下最多能为多少城市供水。

输入的第一行包含三个整数 $n, m, z$ $(1 \leq n, m, z \leq 100000)$，分别表示南北向河流数、东西向河流数和操作次数。 第二行是一个长度为 $n$ 的字符串，由 `+` 和 `-` 组成；第 $i$ 个字符表示第 $i$ 条南北向河流的状态：`+` 表示干净，`-` 表示污染。第三行是一个长度为 $m$ 的字符串，以相同格式描述东西向河流的初始状态。 接下来的 $z$ 行描述操作，每行格式为以下之一： - $\texttt{Z}\ c$：询问在预算 $c$ $(0 \leq c \leq 10^{18})$ 下，最多能为多少城市供水； - $\texttt{N}\ i$：第 $i$ $(1 \leq i \leq n)$ 条南北向河流状态改变（干净变为污染，或污染变为干净）； - $\texttt{M}\ i$：第 $i$ $(1 \leq i \leq m)$ 条东西向河流状态改变。

对于每个 $\texttt{Z}$ 类型的询问，输出一行一个整数，表示在给定预算下最多能供水的城市数量。

**样例 1 解释** 初始状态下，实线表示干净河流，虚线表示污染河流，共有 $12$ 座城市位于交点处。  第一个询问 $\texttt{Z}\ 1$：城市 $(1,4)$ 和 $(2,4)$ 的运水成本为 $1$，因此只能放弃一座，其余 $10$ 座成本为 $0$，故答案为 $11$。 操作 $\texttt{M}\ 1$、$\texttt{M}\ 2$、$\texttt{M}\ 3$ 后，仅 $4$ 座城市有直接干净河流。询问 $\texttt{Z}\ 7$：预算 $7$ 可额外为 $x=2$ 上的 $4$ 座和 $x=1$ 上的 $1$ 座供水，总计 $9$ 座。 **附加样例** 1. 该样例满足 $n=m=11$，仅第 $6$ 条南北向和东西向河流干净，询问预算 $0, 1, \ldots, 220$； 2. 该样例满足 $n=100000, m=1$，每次询问时恰有一条干净河流（对 $1 \leq i \leq 33333$，先净化第 $3i$ 条河流，询问成本 $2500000000$，再污染第 $3i$ 条河流）。 详细子任务附加限制及分值如下表所示。 | 子任务编号 | 附加限制 | 分值 | | :---: | :--: | :---: | | $1$ | $n, m, z \leq 100$ | $7$ | | $2$ | 每条东西向河流始终污染 | $7$ | | $3$ | $n, m, z \leq 1000$ | $21$ | | $4$ | 询问预算总和不超过 $10^{9}$ | $21$ | | $5$ | 无附加限制 | $44$ |