[R57F]YourName - 代码源竞赛平台

时空限制

2S/512M

题目描述

你的名字

我不想再在时间里捉迷藏
和你走散
还是到最后了呢。
这题为什么和名字无关？
因为已忘记了，也已丢失了。

有 $n$ 个物品，当前按某种顺序排成一列。第 $i$ 个位置上的物品标签为 $P_i$。其中 $P$ 是一个 $1 \sim n$ 的一个排列。

对于每个 $k$ ，$W_k$ 表示搬运标签为 $k$ 的物品所需的代价。

你可以进行若干次操作。每次操作中，可以从当前序列中任选一个物品，将它移动到序列的最前端或最后端。如果本次移动的物品标签为 $k$，则需要支付代价 $W_k$。同一个物品可以被移动多次；若某个物品被重复移动，则每次移动都需要支付一次对应的代价。

现在有以下两种修改操作：

• 1 x y：交换当前序列中第 $x$ 个位置与第 $y$ 个位置上的物品；即交换二者的标签。
• 2 i v：将标签为 $i$ 的物品的搬运代价修改为 $v$。

你需要输出对于每次修改后，如果要将物品的的标签按照升序排序，所需要的最小代价。

格式

输入格式

第一行包含两个整数 $n,q$，分别表示物品个数和修改操作次数。

第二行包含 $n$ 个整数 $P_1,P_2,\dots,P_n$，表示当前序列中各个位置上的物品标签。其中，第 $i$ 个位置上的物品标签为 $P_i$。

第三行包含 $n$ 个整数 $W_1,W_2,\dots,W_n$，其中 $W_i$ 表示标签为 $i$ 的物品的搬运代价。

接下来 $q$ 行，每行描述一次修改操作，格式如下：

• 1 x y：交换当前序列中第 $x$ 个位置和第 $y$ 个位置上的物品；
• 2 i v：将标签为 $i$ 的物品的搬运代价修改为 $v$。

输出格式

输出共 $q+1$ 行。

• 第 $1$ 行输出初始状态下，将当前序列调整为升序排列所需的最小代价；
• 第 $2$ 到第 $q+1$ 行依次输出每次修改操作后，对应状态下将当前序列调整为升序排列所需的最小代价。

样例

样例输入 #1

5 3
3 1 4 2 5
10 20 30 40 50
1 1 4
2 4 100
1 2 5

样例输出 #1

30
60
60
110

样例解释 #1

1. 初始状态

• 当前序列：[3, 1, 4, 2, 5]
• 最优操作过程：

1. 将标签 $2$ 移动到最前端，序列变为 [2, 3, 1, 4, 5]，花费 $W_2=20$。
2. 将标签 $1$ 移动到最前端，序列变为 [1, 2, 3, 4, 5]，花费 $W_1=10$。

• 总代价为：$20 + 10 = 30$。

2. 第一次操作：1 1 4

• 当前序列：[2, 1, 4, 3, 5]
• 最优操作过程：

1. 将标签 3 移动到最前端，序列变为 [3, 2, 1, 4, 5]，花费 $W_3=30$。
2. 将标签 2 移动到最前端，序列变为 [2, 3, 1, 4, 5]，花费 $W_2=20$。
3. 将标签 1 移动到最前端，序列变为 [1, 2, 3, 4, 5]，花费 $W_1=10$。

• 总代价为：$30 + 20 + 10 =60$。

3. 第二次操作：2 4 100

• 当前序列：[2, 1, 4, 3, 5]
• 最优操作过程：

1. 将标签 $3$ 移到最前，花费 $W_3=30$。
2. 将标签 $2$ 移到最前，花费 $W_2=20$。
3. 将标签 $1$ 移到最前，花费 $W_1=10$。

• 总代价为：$30 + 20 + 10 =60$。

4. 第三次操作：1 2 5

• 当前序列：[2, 5, 4, 3, 1]
• 最优操作过程：

1. 将标签 $5$ 移动到最后端，序列变为 [2, 4, 3, 1, 5]，花费 $W_5=50$。
2. 将标签 $3$ 移动到最前端，序列变为 [3, 2, 4, 1, 5]，花费 $W_3=30$。
3. 将标签 $2$ 移动到最前端，序列变为 [2, 3, 4, 1, 5]，花费 $W_2=20$。
4. 将标签 $1$ 移动到最前端，序列变为 [1, 2, 3, 4, 5]，花费 $W_1=10$。

• 总代价为：$50 + 30 + 20 + 10 =110$。

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n,q\le$
$1$	$50$	$2000$
$2$	$50$	$2 \times 10^5$

对于 $100\%$ 的数据，$2 \le n \le 2 \times 10^5$，$1 \le q \le 2 \times 10^5$，$1 \le W_i \le 10^9$，$1 \le x, y \le n$ 且 $x \not = y$，$1 \le i \le n$，$1 \le v \le 10^9$，$1 \le P_i \le n$，保证 $P$ 始终为排列。