P10684 [COTS 2024] 分割 Segregacija

译自 [Izborne Pripreme 2024 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2024/) D2T2。$\texttt{5s,512M}$。 **请不要滥用本题评测。滥用本题评测将被封号。**

Pero 有一个 $2$ 行 $N$ 列的矩阵，每个格子里有一个红球或蓝球。 Pero 想要重排矩阵中的球，使得所有蓝球位于矩阵的左上侧，所有红球位于右下侧。更为具体地说，重排后，不能存在一个红球位于某个蓝球的上方或左侧。 为此，Pero 可以多次交换相邻的两个球。**两个球是相邻的当且仅当它们所在的格子有公共边。** Pero 想知道达到目标所需的最少交换次数。 此外，Pero 会交换矩阵中的相邻两个球 $Q$ 次，并在每次变更后询问当前矩阵状态所需的最小交换次数。请帮助 Pero，输出初始矩阵下以及每次交换后所需的最小交换次数。

第一行，两个整数 $N,Q$，含义见题面。 接下来两行，每行一个长度为 $N$ 的字符串，描述这个矩阵。其中 $\texttt{C}$ 代表红球，$\texttt{P}$ 代表蓝球。 接下来 $Q$ 行，每行三个正整数 $t,x,y$，描述一次交换操作。 - $t=1$ 时，表示交换 $(x,y),(x,y+1)$； - $t=2$ 时，表示交换 $(x,y),(x+1,y)$。 保证交换的两个位置都在矩阵内。

输出 $(Q+1)$ 行，分别表示初始矩阵的答案和每次修改后的答案。

#### 样例解释 样例 $1$ 解释：对于初始状态，只需要依次交换 $(1,1),(2,1)$，$(1,3),(1,4)$，$(1,4),(2,4)$ 即可。 #### 数据范围 对于 $100\%$ 的数据，保证 $1\le N\le 10^6$，$0\le Q\le 10^6$。 | 子任务编号 | 分值 | 约束 | |:-----:|:------:|:-------:| | $1$ | $7$ | $N\le 10$ | | $2$ | $11$ | 最多只有 $10$ 个 $\texttt{C}$ | | $3$ | $17$ | $N,Q\le 500$ | | $4$ | $10$ | $N,Q\le 5\, 000$ | | $5$ | $13$ | $N\le 100\, 000, Q\le 100$ | | $6$ | $15$ | $t=2$ | | $7$ | $27$ | 无额外约束 |