← 返回题目列表

Codeforces · 2206/J

J. 全球播放列表

中文机器翻译题面 查看原题

您正在计划环游世界。在这次旅行中,您安装了一个音乐应用程序,其中包含 $$$n$$$ 歌曲,编号从 $$$1$$$ 到 $$$n$$$。

最初,应用程序会以 $$$1, 2, \ldots, n$$$ 排列的形式为这些 $$$n$$$ 歌曲生成播放列表,用 $$$a_1, a_2, \ldots, a_n$$$ 表示。它按照 $$$a_1、a_2、\ldots、a_n$$$ 的顺序播放 $$$n$$$ 歌曲:首先播放歌曲 $$$a_1$$$,其次播放歌曲 $$$a_2$$$,依此类推。播放列表是 无限:每次播放歌曲 $$$a_n$$$ 后,都会从歌曲 $$$a_1$$$ 开始。

当前歌曲播放完毕后,自动开始播放下一首歌曲。在一首歌曲结束之前,您可以按 跳过 按钮可立即跳转到播放列表中的下一首歌曲。

您有 $$$n$$$ 歌曲的所需排列,用 $$$b_1、b_2、\ldots、b_n$$$ 表示。这意味着您想听 $$$n$$$ 歌曲 完整 按 $$$b_1、b_2、\ldots、b_n$$$ 的顺序,策略性地按跳过按钮零次或多次。换句话说,您希望完整收听(不跳过)的第一首歌曲是歌曲 $$$b_1$$$,第二首歌曲是歌曲 $$$b_2$$$,依此类推,直到第 $$$n$$$ 是歌曲 $$$b_n$$$。完整听完这些 $$$n$$$ 歌曲后,你就不再听了。

您使用此播放列表 $$$d$$$ 天。在每对连续的日子之间,您可以使用三个整数 $$$c$$$、$$$x$$$ 和 $$$y$$$ 更新排列,如下所示:

  • 如果 $$$c = 1$$$,则交换 $$$a_x$$$ 和 $$$a_y$$$。
  • 如果$$$c = 2$$$,则交换$$$b_x$$$ 和$$$b_y$$$。

请注意,每次更新的效果都会持续到随后的几天。

假设您每天从歌曲 $$$a_1$$$ 开始收听,请确定您需要按跳过按钮的最少次数,以便您完整收听的歌曲按此顺序为 $$$b_1、b_2、\ldots、b_n$$$。

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$d$$$ ($$$2 \le n \le 200\,000$$$; $$$2 \le d \le 200\,000$$$)。

第二行包含 $$$n$$$ 整数,表示 $$$a_1、a_2、\ldots、a_n$$$ 的初始值($$$1 \le a_i \le n$$$;$$$a_i \neq a_j$$$ 对于所有 $$$i \neq j$$$)。

第三行包含 $$$n$$$ 整数,表示 $$$b_1、b_2、\ldots、b_n$$$ 的初始值($$$1 \le b_i \le n$$$;$$$b_i \neq b_j$$$ 对于所有 $$$i \neq j$$$)。

接下来的 $$$d-1$$$ 行的第 $$$k$$$ 行包含三个整数 $$$c$$$、$$$x$$$ 和 $$$y$$$ ($$$c \in \{1, 2\}$$$; $$$1 \le x \lt y \le n$$$),表示第 $$$k$$$ 行和第 $$$k$$$ 行之间的更新第 $$$(k+1)$$$ 天。

输出

输出 $$$d$$$ 行,其中第 $$$k$$$ 行应包含第 $$$k$$$ 天的最小跳过次数。

示例

输入
复制

4 3
1 4 2 3
3 2 1 4
1 3 4
2 1 3

输出
复制

6
2
6

输入
复制

7 5
4 7 1 2 6 5 3
2 6 5 1 4 3 7
1 2 5
2 6 7
1 6 7
2 1 5

输出
复制

16
26
21
20
6

注意

示例输入/输出#1 的说明

第一天,$$$(a_1, \ldots, a_4) = (1, 4, 2, 3)$$$ 和 $$$(b_1, \ldots, b_4) = (3, 2, 1, 4)$$$。您可以按所需顺序完整收听这些歌曲,并跳过 $$$6$$$:

  • 播放歌曲 $$$1$$$。跳过这首歌。
  • 播放歌曲 $$$4$$$。跳过这首歌。
  • 播放歌曲 $$$2$$$。跳过这首歌。
  • 播放歌曲 $$$3$$$。完整地听这首歌。
  • 播放歌曲 $$$1$$$。跳过这首歌。
  • 播放歌曲 $$$4$$$。跳过这首歌。
  • 播放歌曲 $$$2$$$。完整地听这首歌。
  • 播放歌曲 $$$3$$$。跳过这首歌。
  • 播放歌曲 $$$1$$$。完整地听这首歌。
  • 播放歌曲 $$$4$$$。完整地听这首歌。

第二天,排列为 $$$(a_1, \ldots, a_4) = (1, 4, \mathbf{3}, \mathbf{2})$$$ 和 $$$(b_1, \ldots, b_4) = (3, 2, 1, 4)$$$。最少跳过次数为 $$$2$$$。

第三天,排列为 $$$(a_1, \ldots, a_4) = (1, 4, 3, 2)$$$ 和 $$$(b_1, \ldots, b_4) = (\mathbf{1}, 2, \mathbf{3}, 4)$$$。最少跳过次数为 $$$6$$$。