UOJ Logo Universal Online Judge

UOJ

#971. 【JOISC2025】集邮比赛 4

附件下载 统计

在湖泊周围,有 2N 个均匀分布的地点,按顺时针方向编号为 12N。此外,还有 2N单向道路连接相邻的地点。道路 i1i2N1)从地点 i 通往地点 i+1,而道路 2N 从地点 2N 通往地点 1。每条道路的中点处设有一个印章台。

共有 N 种颜色的印章,编号为 1N。在道路 i1i2N)的印章台上可以获得的印章颜色为 Ai。对于每种颜色 j1jN),恰好有 2 个印章台提供该颜色的印章。

JOI 君携带了多张集章卡参加比赛。每张集章卡有左、右两个空格,可以加盖印章。每个空格最多加盖一枚印章。初始时,所有集章卡均为空白。

JOI 君参加集章拉力赛的流程如下:

  1. 首先,选择 2N 个地点中的一个作为起点,并移动至该地点。若选择地点 i1i2N),则需要支付参与费用 Ci
  2. 接着,他可以指令主办方交换相邻的印章台。具体来说,可以交换道路 2N1 的印章台,或者交换道路 i1i 的印章台(2i2N)。每次交换需花费 X,JOI 君可以执行任意多次的交换(包括零次)。交换操作会在指令下达后立即执行。但为了防止作弊,不允许交换跨越 JOI 君所选起点的印章台。即:
    • 若起点为地点 1,则禁止交换道路 2N1 的印章台。
    • 若起点为地点 i2i2N),则禁止交换道路 i1i 的印章台。
  3. 此后,JOI 君从所选起点出发,按顺时针方向依次访问 2N 个印章台。访问印章台时,他可以任意次地在该台为集章卡盖章。同一张卡可以在同一台同时加盖左、右两格。但每张集章卡必须先在左空格盖章,之后才能在右空格盖章,即若某卡的左空格未盖章,则不能在该卡的右空格盖章。

JOI 君想要收集尽可能多不同类型的已盖章卡。定义盖章卡 (a,b) 为左空格为颜色 a、右空格为颜色 b 的集章卡。

当且仅当 a1=a2b1=b2 时,盖章卡 (a1,b1)(a2,b2) 被视为同一种类型。

由于共有 N 种颜色,因此总共有 N2 种可能的盖章卡类型。

Q 个查询。第 q 个查询(1qQ)的内容如下: - 若要使得 JOI 君在拉力赛结束时收集到至少 Kq 种类型的盖章卡,所需的最小总成本是多少?

可以证明,在给定的约束条件下,JOI 君总能通过足够大的成本收集到至少 Kq 种类型的盖章卡。

编程回答 JOI 君的 Q 个查询。

输入格式

  • N X
  • A1 A2 A2N
  • C1 C2 C2N
  • Q
  • K1
  • K2
  • KQ

输出格式

输出 Q 行,其中第 q 行(1qQ)包含收集至少 Kq 种类型盖章卡所需的最小总成本。

输入 #1

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

输出 #1

3
4

explanation

考虑 JOI 君选择地点 2 作为起点,并指令交换道路 34 上印章台的情况: - JOI 君支付的总成本为 C2+X×1=3。 - JOI 君按道路 234561 的顺序访问印章台,各台可获得的印章颜色依次为 2,3,2,1,3,1。 - JOI 君可收集的双空格盖章卡类型数为 8 种。 ◦ 例如,要获得左格为颜色 3、右格为颜色 1 的盖章卡,JOI 君可在道路 3 的台加盖左格,在道路 1 的台加盖右格。 ◦ 但需注意,无法获得左格为颜色 1、右格为颜色 2 的盖章卡。

由于无法以 2 或更低的成本获得 8 种及以上类型的盖章卡,输出的第一行应为 3

此外,若 JOI 君选择地点 3 作为起点且不进行任何印章台交换,他可获得 9 种类型的盖章卡: - 此时 JOI 君支付的总成本为 C3+X×0=4。由于无法以 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

输出 #2

7

explanation

考虑 JOI 君选择地点 10 作为起点,并按以下顺序交换印章台: 1. 交换道路 1516 的印章台; 2. 交换道路 23 的印章台; 3. 交换道路 161 的印章台; 4. 交换道路 12 的印章台。

此时 JOI 君可获得 64 种类型的盖章卡,支付的总成本为 C10+X×4=7

该样例满足子任务 26 的限制。

输入 #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

输出 #3

1
18
3
10
1
1

explanation

该样例满足子任务 4,6 的限制。

数据范围

  • 2N500000
  • 1X500000
  • (A1,A2,,A2N)(1,1,2,2,,N,N) 的一个排列。
  • 1Ci10181i2N)。
  • 1Q500000
  • 1KqN21qQ)。
  • 所有输入值为整数。

子任务

  • Subtask 1 (5 pts)N4
  • Subtask 2 (20 pts)N5000Q=1K1=N2
  • Subtask 3 (20 pts)N5000Q=1
  • Subtask 4 (19 pts)N5000
  • Subtask 5 (21 pts)Q=1
  • Subtask 6 (15 pts):无额外限制。