当前没有测试数据。

F - 排序颜色球

分数：$500$ 点

问题描述

有 $N$ 个球从左到右排列。 第 $i$ 个球的颜色是颜色 $C_i$，球上写着一个整数 $X_i$。

Takahashi 想要重新排列球，使得球上写的整数从左到右是非递减的。 换句话说，他的目标是使得对于所有的 $1\leq i\leq N-1$，第 $i+1$ 个球上的数字大于等于第 $i$ 个球上的数字。

为此，Takahashi 可以任意多次（可能是零次）执行以下操作：

选择一个整数 $i$，使得 $1\leq i\leq N-1$。
如果第 $i$ 个球和第 $i+1$ 个球的颜色不同，需要支付成本为 $1$。 （如果颜色相同则不需要支付成本）
交换第 $i$ 个球和第 $i+1$ 个球的位置。

找出 Takahashi 达到目标所需的最小总成本。

约束

• $2 \leq N \leq 3\times 10^5$
• $1\leq C_i\leq N$
• $1\leq X_i\leq N$
• 输入中的所有值都是整数。

输入

从标准输入中以下列格式给出：

$N$

$C_1$ $C_2$ $\ldots$ $C_N$

$X_1$ $X_2$ $\ldots$ $X_N$

输出

将 Takahashi 达到目标所需的最小总成本以整数形式输出。

5
1 5 2 2 1
3 2 1 2 1

6

我们将一个球表示为 $(\text{颜色}, \text{整数})$。 初始情况为 $(1,3)$, $(5,2)$, $(2,1)$, $(2,2)$, $(1,1)$。 以下是 Takahashi 可能的一系列操作：

• 交换第 $1$ 个球（颜色为 $1$）和第 $2$ 个球（颜色为 $5$），此时球的顺序变为 $(5,2)$, $(1,3)$, $(2,1)$, $(2,2)$, $(1,1)$。
• 交换第 $2$ 个球（颜色为 $1$）和第 $3$ 个球（颜色为 $2$），此时球的顺序变为 $(5,2)$, $(2,1)$, $(1,3)$, $(2,2)$, $(1,1)$。
• 交换第 $3$ 个球（颜色为 $1$）和第 $4$ 个球（颜色为 $2$），此时球的顺序变为 $(5,2)$, $(2,1)$, $(2,2)$, $(1,3)$, $(1,1)$。
• 交换第 $4$ 个球（颜色为 $1$）和第 $5$ 个球（颜色为 $1$），此时球的顺序变为 $(5,2)$, $(2,1)$, $(2,2)$, $(1,1)$, $(1,3)$。
• 交换第 $3$ 个球（颜色为 $2$）和第 $4$ 个球（颜色为 $1$），此时球的顺序变为$(5,2)$, $(2,1)$, $(1,1)$, $(2,2)$, $(1,3)$。
• 交换第 $1$ 个球（颜色为 $5$）和第 $2$ 个球（颜色为 $2$），此时球的顺序变为 $(2,1)$, $(5,2)$, $(1,1)$, $(2,2)$, $(1,3)$。
• 交换第 $2$ 个球（颜色为 $5$）和第 $3$ 个球（颜色为 $1$），此时球的顺序变为 $(2,1)$, $(1,1)$, $(5,2)$, $(2,2)$, $(1,3)$。

在最后一次操作之后，从左到右球上写的整数依次为 $1,1,2,2,3$，Takahashi的目标达成。

第 $1$、$2$、$3$、$5$、$6$、$7$ 次操作分别产生 $1$ 的成本，总计为 $6$，也就是最小成本。 注意第 $4$ 次操作没有产生成本，因为两个球的颜色都是 $1$。

3
1 1 1
3 2 1

0

所有的球都是同一种颜色，因此交换球不需要成本。

3
3 1 2
1 1 2

0

Takahashi的目标已经在初始情况下实现，无需进行任何操作。