Public Judge

pjudge

Time Limit: 3 s Memory Limit: 2048 MB Total points: 100
统计

题目描述

有一个 $2\times n$ ($2$ 行 $n$ 列)的棋盘,棋盘上每个格子都放着一颗巧克力豆或一颗豌豆。

对于一个初始局面,你可以做若干次交换,每次交换形如:

  • 选择两个有公共边的格子,交换这两个格子上的豆子。

你需要使得最终局面中所有的豌豆都在棋盘的左上方。具体来说:

  • 对于第一行与第二行:同行中,所有豌豆在巧克力豆的左方(即为一个前缀)。
  • 设第一行有 $x$ 个豌豆,第二行有 $y$ 个豌豆,则 $x\ge y$。

C 为巧克力豆,P 为豌豆,则以下是一个可能的最终局面:

PPPPC
PCCCC

你想要经过若干次交换,使得所有的豌豆都在棋盘的左上方。

有 $q$ 次询问,每次会交换初始状态中相邻格子上的豆子。

你需要在第一次交换前和每次交换后,对于这 $q+1$ 种初始状态,分别求出至少需要多少次交换才能使所有的豌豆都在棋盘的左上方。

输入格式

第一行两个整数 $n,q$。

接下来两行,每行一个长度为 $n$ 的字符串,表示初始状态的棋盘。其中 C 为巧克力豆,P 为豌豆。

接下来 $q$ 行,每行三个整数 $op,x,y$。

  • $op=1$:交换 $(x,y)$ 和 $(x,y+1)$ 的豆子。
  • $op=2$:交换 $(x,y)$ 和 $(x+1,y)$ 的豆子。
  • 保证所在的两个格子存在于棋盘内。

输出格式

输出 $q+1$ 行,表示对于 $q+1$ 种初始状态的答案。

样例数据

样例输入 1

5 2
CPCPC
PCCPC
1 1 4
1 1 2

样例输出 1

3
4
5

样例解释 1

对于第一个初始状态,交换 (1,1)-(2,1),(1,3)-(1,4),(1,4)-(2,4).

样例输入/输出 2~8

见下发文件。分别满足 Subtask 1~7 的性质。

数据范围

对于所有数据,$1\le n\le 10^6,0\le q\le 10^6$。

子任务编号 特殊性质 分值
$1$ $n\le 10,q\le 10^6$ $8$
$2$ 至多有 $10$ 个 C $12$
$3$ $n,q\le 500$ $16$
$4$ $n,q\le 5000$ $12$
$5$ $n\le 100000,q\le 100$ $16$
$6$ 保证所有操作 $op=2$ $16$
$7$ 无特殊限制 $20$