P3482 [POI 2009] SLO-Elephants

在 Byteotian 动物园，一场大象游行即将开始。动物园的员工鼓励这些庞大的动物排成一列，因为经理希望这是游行的初始形态。不幸的是，经理亲自来到游行现场，对所见的情形并不满意——他原本打算让大象按完全不同的顺序排列。因此，他强制执行了他所设想的顺序，声称这样动物看起来会最为庄严，并让员工按照他的意愿重新排列大象。由于移动大象群可能会造成混乱，员工决定通过一次交换一对大象的方式来重新排列它们。幸运的是，动物们不需要站在一起就可以交换位置。然而，让大象移动并不像听起来那么简单。实际上，所需的努力与动物的质量成正比。因此，交换质量分别为 $m_1$ 和 $m_2$ 的一对大象所需的努力可以估算为 $m_1+m_2$。重新排列大象以符合经理的意愿所需的最小努力是多少？ 编写一个程序： - 从标准输入读取动物园中所有大象的质量，以及它们当前和期望的排列顺序。 - 确定一个大象交换序列，从初始顺序到期望的动物排列顺序，使得这个序列中的所有交换的总努力最小化。 - 在标准输出上打印出总的最小努力。

标准输入的第一行包含一个整数 $n$ ($1 \le n \le 1{,}000{,}000$)，表示动物园中的大象数量。 为了简化问题，我们假设大象的编号从 $1$ 到 $n$。 第二行包含 $n$ 个整数 $m_i$ ($100 \le m_i \le 6{,}500$ 对于 $1 \le i \le n$)，用空格分隔，表示各个大象的质量（单位：千克）。 输入的第三行包含 $n$ 个两两不同的整数 $a_i$ ($1 \le a_i \le n$)，用空格分隔，表示初始排列中连续大象的编号。 第四行包含 $n$ 个两两不同的整数 $b_i$ ($1 \le b_i \le n$)，用空格分隔，表示动物园经理期望的排列中连续大象的编号。可以假设序列 $(a_i)$ 和 $(b_i)$ 是不同的。

标准输出的第一行应包含一个整数，表示将大象从序列 $(a_i)$ 表示的顺序重新排列到 $(b_i)$ 表示的顺序所需的最小总努力。

题面翻译由 ChatGPT-4o 提供。