[COTS 2024] 分割 Segregacija

Luogu

IDLGP10684

Time5000ms

Memory512MB

DifficultyP7

贪心线段树2024O2优化COTS（克罗地亚）

Pero 有一个 $2$ 行 $N$ 列的矩阵，每个格子里有一个红球或蓝球。 Pero 想要重排矩阵中的球，使得所有蓝球位于矩阵的左上侧，所有红球位于右下侧。更为具体地说，重排后，不能存在一个红球位于某个蓝球的上方或左侧。为此，Pero 可以多次交换相邻的两个球。**两个球是相邻的当且仅当它们所在的格子有公共边。** Pero 想知道达到目标所需的最少交换次数。此外，Pero 会交换矩阵中的相邻两个球 $Q$ 次，并在每次变更后询问当前矩阵状态所需的最小交换次数。请帮助 Pero，输出初始矩阵下以及每次交换后所需的最小交换次数。 ## Input 第一行，两个整数 $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)$。保证交换的两个位置都在矩阵内。 ## Output 输出 $(Q+1)$ 行，分别表示初始矩阵的答案和每次修改后的答案。 [samples] ## Background 译自 [Izborne Pripreme 2024 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2024/) D2T2。$\texttt{5s,512M}$。 **请不要滥用本题评测。滥用本题评测将被封号。** ## Note #### 样例解释样例 $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$ | 无额外约束 |

Samples

Input #1

5 2
CPCPC
PCCPC
1 1 4
1 1 2

Output #1

3
4
5

Input #2

5 0
CPPCC
PPCCP

Output #2

Input #3

10 7
CCPPPCCPCP
PPPCCCPCCC
1 2 7
2 1 4
2 1 8
1 1 9
2 1 1
1 2 7
1 1 4

Output #3

API Response (JSON)

{
  "problem": {
    "name": "[COTS 2024] 分割 Segregacija",
    "description": {
      "content": " Pero 有一个 $2$ 行 $N$ 列的矩阵，每个格子里有一个红球或蓝球。 Pero 想要重排矩阵中的球，使得所有蓝球位于矩阵的左上侧，所有红球位于右下侧。更为具体地说，重排后，不能存在一个红球位于某个蓝球的上方或左侧。 为此，Pero 可以多次交换相邻的两个球。**两个球是相邻的当且仅当它们所在的格子有公共边。** Pero 想知道达到目标所需的最少交换次数。 此外，Pero 会交换矩",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 5000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10684"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Pero 有一个 $2$ 行 $N$ 列的矩阵，每个格子里有一个红球或蓝球。\n\nPero 想要重排矩阵中的球，使得所有蓝球位于矩阵的左上侧，所有红球位于右下侧。更为具体地说，重排后，不能存在一个红球位于某个蓝球的上方或左侧。\n\n为此，Pero 可以多次交换相邻的两个球。**两个球是相邻的当且仅当它们所在的格子有公共边。** Pero 想知道达到目标所需的最少交换次数。\n\n此外，Pero 会交换矩阵...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments