AdditionalFile5048.zip

#5048. 「JOISC 2025 Day2」邮戳拉力赛 4

标签: 传统 | 时间限制: 3000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 JOISC 2025 Day2 T2 「スタンプラリー 4 / Collecting Stamps 4」

JOI 君居住的 IOI 国以其壮丽的大湖闻名。今天，湖边将举办一场别开生面的集章大会。

湖周围均匀分布着 $2N$ 个地点，沿顺时针方向依次编号为 $1$ 到 $2N$。相邻地点间有 $2N$ 条单行道连接：道 $i$ $(1 \leq i \leq 2N-1)$ 从地点 $i$ 通向 $i+1$，道 $2N$ 从地点 $2N$ 通向地点 $1$。每条道的中间设有一个集章台。

集章共有 $N$ 种颜色，编号为 $1$ 到 $N$。道 $i$ $(1 \leq i \leq 2N)$ 的集章台提供颜色 $A_i$ 的印章，且每种颜色 $j$ $(1 \leq j \leq N)$ 在正好两个集章台出现。

JOI 君带着一堆集章卡参加大会。每张卡上有左右两个框，每个框最多盖一个章。初始时，卡片都是空白的。他的行动步骤如下：

1. 首先，从 $2N$ 个地点中选一个作为起点，前往那里。若选地点 $i$ $(1 \leq i \leq 2N)$，需支付参赛费用 $C_i$。
2. 接下来，可以指示运营公司交换相邻道上的集章台。例如，交换道 $2N$ 和道 $1$，或指定 $i$ $(2 \leq i \leq 2N)$ 交换道 $i-1$ 和道 $i$。每次调整成本为 $X$，可多次调整或不调整，调整即时生效。但为防作弊，不能交换跨越起点的集章台：若起点为地点 $1$，则禁止交换道 $2N$ 和道 $1$；若为地点 $i$ $(2 \leq i \leq 2N)$，则禁止交换道 $i-1$ 和道 $i$。
3. 在这之后，从起点顺时针移动，依次访问 $2N$ 个集章台，返回起点后结束。每次访问可随意盖章，甚至在同一集章台为一张卡的左右框盖章，但必须按左、右顺序盖，不能跳过左侧直接盖右侧。

JOI 君希望收集尽可能多类型的满章卡（左右框均盖章）。将左框颜色为 $a$、右框颜色为 $b$ 的卡记为 $(a, b)$，仅当 $a_1 = a_2$ 且 $b_1 = b_2$ 时，卡 $(a_1, b_1)$ 和 $(a_2, b_2)$ 视为同类型。$N$ 种颜色意味着满章卡共有 $N^2$ 种。

你需要帮助 JOI 君回答 $Q$ 个问题。第 $q$ $(1 \leq q \leq Q)$ 个问题是：在集章结束时，收集至少 $K_q$ 种满章卡所需的最小总成本是多少？题目保证在约束下，支付足够成本可收集 $K_q$ 种以上。

给你印章颜色、参赛费用、调整成本及 JOI 君的问题，编写程序计算 $Q$ 个答案。

输入格式

第一行包含两个整数 $N,X$。

第二行包含用空格分隔的 $2N$ 个整数 $A_1, A_2, \ldots ,A_{2N}$。

第三行包含用空格分隔的 $2N$ 个整数 $C_1, C_2, \ldots ,C_{2N}$。

第四行包含一个整数 $Q$。

接下来的 $Q$ 行，每行包含一个整数 $K_i$。

输出格式

输出 $Q$ 行。第 $q$ $(1 \leq q \leq Q)$ 行输出收集至少 $K_q$ 种满章卡所需的最小总成本。

样例 1

输入

3 2
1 2 2 3 1 3
6 1 4 5 4 7
2
8
9

输出

3
4

若 JOI 君选地点 $2$ 为起点，并交换道 $3$ 和道 $4$ 的集章台：

• 总成本：$C_2 + X \times 1 = 1 + 2 = 3$
• 访问顺序为道 $2, 3, 4, 5, 6, 1$，颜色依次为 $2, 3, 2, 1, 3, 1$
• 可得 $8$ 种满章卡，如 $(3,1)$ 在道 $3$ 盖左框、道 $1$ 盖右框
• 无法得 $(1,2)$，成本 $2$ 以下无法集齐 $8$ 种，故输出 $3$

若选地点 $3$，不交换：

• 总成本：$C_3 + X \times 0 = 4$
• 可得 $9$ 种满章卡，成本 $3$ 以下无法集齐 $9$ 种，故输出 $4$

这个样例满足子任务 $1,4,6$ 的限制。

样例 2

输入

8 1
1 2 6 1 6 3 8 4 5 5 3 4 7 2 7 8
4 5 3 6 2 9 1 4 6 3 8 5 2 9 4 7
1
64

输出

7

这个样例满足子任务 $2,3,4,5,6$ 的限制。

样例 3

输入

9 4
4 3 5 3 8 1 5 8 1 7 6 2 4 9 6 9 2 7
12 9 4 8 7 1 20 5 8 7 4 13 5 9 10 3 7 8
6
39
81
73
79
64
52

输出

1
18
3
10
1
1

这个样例满足子任务 $4,6$ 的限制。

数据范围与提示

对于所有输入数据，满足：

• $2 \leq N \leq 500000$
• $1 \leq X \leq 500000$
• $(A_1, A_2, \ldots, A_{2N})$ 是 $(1, 1, 2, 2, \ldots, N, N)$ 的排列
• $1 \leq C_i \leq 10^{18} \, (1 \leq i \leq 2N)$
• $1 \leq Q \leq 500000$
• $1 \leq K_q \leq N^2 \, (1 \leq q \leq Q)$
• 所有输入值均为整数

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$5$	$N \leq 4$
$2$	$20$	$N \leq 5000, Q = 1, K_1 = N^2$
$3$	$20$	$N \leq 5000, Q = 1$
$4$	$19$	$N \leq 5000$
$5$	$21$	$Q = 1$
$6$	$15$	无附加限制