← 返回题目列表

Codeforces · 1368/H2

H2. 面包板容量(硬版)

中文机器翻译题面 查看原题

这是带有修改查询的问题 H 的更难版本。

莱斯特和德尔伯特在一家电子公司工作。他们目前正在开发一种微芯片组件,用于连接大型超级计算机的两个独立部分。

该组件构建在面包板的顶部 - 微芯片的网格状底座。面包板有 $$$n$$$ 行和 $$$m$$$ 列,每个行列交集包含一个节点。此外,面包板的每一侧都有可以连接到相邻节点的端口。左侧和右侧各有 $$$n$$$ 端口,顶部和底部各有 $$$m$$$ 端口。每个端口在外部连接到由面包板桥接的部件之一,并且分别为红色或蓝色。

端口可以通过面包板内部的电线进行连接。但是,有一些规则需要遵循:

- 每根电线应连接一个红色端口和一个蓝色端口,并且每个端口最多应连接到一根电线。
- 电线的每一部分都应水平或垂直,并且只能在其中一个节点处转弯。
- 为了避免干扰,电线不能有非零长度的公共部分(但可以有公共节点)。此外,一根电线不能两次覆盖同一个非零长度的线段。

面包板的容量是根据上述规则可以进行的最大红蓝线连接数。例如,上面的面包板的容量为 $$$7$$$,建立七个连接的一种方法如下图所示。

到目前为止,两个版本的声明是相同的。差异如下。

众所周知,项目的规格在开发过程中发生了很大变化,因此端口的颜色尚未固定。有$$$q$$$个修改需要处理,每个修改的形式都是“沿着一侧的连续范围内的所有端口的颜色被切换(红色变成蓝色,蓝色变成红色)”。所有修改都是持久的,也就是说,在进行下一个修改之前,之前的修改不会撤消。

为了估计更改的严重程度,Lester 和 Delbert 需要找出每次更改后的面包板容量。帮助他们有效地做到这一点。

输入

第一行包含三个整数 $$$n, m, q$$$ ($$$1 \leq n, m \leq 10^5$$$, $$$0 \leq q \leq 10^5$$$) — 面包板的行数和列数,以及修改次数。

接下来的四行描述端口的初始颜色。这些行中的每个字符都是 R 或 B,具体取决于相应端口的颜色。前两行各包含$$$n$$$字符,从上到下分别描述左右两侧的端口。最后两行各包含$$$m$$$字符,从左到右分别描述上下两侧的端口。

接下来的 $$$q$$$ 行描述修改。每行都包含一个字符 $$$s$$$,后跟两个整数 $$$l$$$ 和 $$$r$$$。如果$$$s$$$为L或R,则修改分别涉及左/右侧端口,$$$l$$$和$$$r$$$满足$$$1 \leq l \leq r \leq n$$$,并且侧面$$$l$$$和$$$r$$$(含)之间的行端口切换颜色。同样,如果$$$s$$$为U或D,则$$$1 \leq l \leq r \leq m$$$以及上/下侧$$$l$$$和$$$r$$$(含)之间的列中的端口分别切换颜色。

输出

打印 $$$q + 1$$$ 整数,每行一个 - 对初始着色进行 $$$0、\ldots、q$$$ 修改后的面包板容量。

示例

输入 #1

4 5 4
BBRR
RBBR
BBBBB
RRRRR
L 2 3
R 3 4
U 1 5
D 1 5

输出 #1

7
7
9
4
9