← 返回题目列表

AtCoder · pakencamp_2019_day3_g

G. 当前分布2

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

配点: 100 点

問題文

E869120 您是“AtCoder 圣诞老人办公室”的员工,您每年的工作就是让圣诞老人高效地分发礼物。

嗯,今年圣诞节又到了。他今年的工作是获取圣诞老人的位置和“AtCoder Street”上的房屋信息,让圣诞老人的礼物分发更加高效。

AtCoder 一条街道从西向东延伸,长度 1 \ 000 \ 000 \ 000 路。最初,E869120 中有关房屋位置和圣诞老人​​位置的信息如下。

  • 房子就是这样 N 有屋檐。在家 它的编号为 1, 2, ..., N ,编号 i 房子位于道路西端。 A_i 以米为单位。
  • 就这样,圣诞老人 M 有人。致圣诞老人 1, 2, ..., M ,编号 i 圣诞老人正从路的西端走来。 B_i 我位于几米的位置。

然而,在AtCoder街上,房子经常搬家,圣诞老人搬家等等。因此,到了圣诞节 Q 信息将发生变化。i 关于第二次信息变更,

  • T_i = 1 :数量 C_i 房子的位置位于道路的西端。 D_i 位置更改为米。
  • T_i = 2 :数量 C_i 圣诞老人的位置位于道路的西端。 D_i 位置更改为米。

当时, 关于i = 0, 1, 2, ..., Q ,i 请使用第一次更改后的信息立即回答以下问题。

  • 为了将礼物分发到每家每户,M 将圣诞老人的总数加起来并找出他们需要移动多少米。
  • 然而,假设所有圣诞老人总是有足够数量的礼物。
  • 圣诞老人还可以通过移动到房子的位置来分发礼物。不可能从远处扔礼物并分发它们。圣诞老人分发完礼物后不需要返回原来的位置。

然而,“0 “第一次更改后的信息”是指首次输入E869120的信息。

制約

  • 1 \leq N \leq 100 \ 000
  • 1 \leq M \leq 100 \ 000
  • 0 \leq Q \leq 100 \ 000
  • 0 \leq A_i \leq 1 \ 000 \ 000 \ 000, A_i 是偶数
  • 0 \leq B_i \leq 1 \ 000 \ 000 \ 000, B_i 是奇数
  • 1 \leq T_i \leq 2
  • T_i = 1 时,1 \leq C_i \leq N,0 \leq D_i \leq 1 \ 000 \ 000 \ 000 很满意,D_i 是偶数。
  • T_i = 2 时,1 \leq C_i \leq M,0 \leq D_i \leq 1 \ 000 \ 000 \ 000 很满意,D_i 是奇数。
  • 2 两栋房子来到同一位置等信息没有变化。
  • 2 信息中没有任何变化会导致两个圣诞老人处于相同的位置。

部分点

该问题分为多个子任务,如果您正确回答了该子任务中的所有测试用例,则视为您正确回答了该子任务。
提交的源代码的分数是您正确回答的子作业分数的总和。

  1. (2 点) M = 1,Q = 0.
  2. (6 点) M = 2,Q = 0.
  3. (14 点) N \leq 250,M \leq 250,Q = 0.
  4. (9 点) N \leq 3 \ 000,M \leq 3 \ 000,Q = 0.
  5. (9 点) Q = 0.
  6. (35 点) N \leq 40 \ 000, M \leq 40 \ 000, Q \leq 40 \ 000, T_i = 1.
  7. (19 点) N \leq 40 \ 000, M \leq 40 \ 000, Q \leq 40 \ 000.
  8. (6 分) 没有额外的限制。

入力

输入是按以下格式从标准输入给出的。

N
A_1 A_2 A_3 ... A_N
M
B_1 B_2 B_3 ... B_M
Q
T_1 C_1 D_1
T_2 C_2 D_2
T_3 C_3 D_3
: : :
T_Q C_Q D_Q

出力

Q+1 行。 在
i 行中, 请输出第i-1 次更改后信息中圣诞老人总行走距离的最小值。


入力例 1

5
12 18 36 50 68
1
25
0

出力例 1

69

当圣诞老人按如下方式移动时,移动的总距离为 69 ,这是最小值。

  • 圣诞老人 1 到家了 前往 1 并分发礼物。该点行驶的距离为 13 是。
  • 圣诞老人 1 到家了 前往 2 并分发礼物。该点行驶的距离为 19 是。
  • 圣诞老人 1 到家了 前往 3 并分发礼物。该点行驶的距离为 37 是。
  • 圣诞老人 1 到家了 前往 4 并分发礼物。该点行驶的距离为 51 是。
  • 圣诞老人 1 到家了 前往 5 并分发礼物。该点行驶的距离为 69 是。

入力例 2

5
138 218 224 110 146
2
127 157
0

出力例 2

120

此输入示例满足子任务 2 的约束。
对于子任务 2,请使用输入示例 1。 请注意, M = 1 的情况不包括在内。


入力例 3

10
2412 1276 1948 2000 2542 2558 2070 2712 2820 1542
6
3001 1545 1213 2473 2559 2019
0

出力例 3

595

此输入示例满足子任务 3、4 和 5 的约束。 解决


入力例 4

10
2412 1276 1948 2000 2542 2558 2070 2712 2820 1542
6
3001 1545 1213 2473 2559 2019
7
1 2 1348
1 8 3200
2 3 2951
1 4 2102
2 5 1137
1 10 420
2 1 2207

出力例 4

595
667
866
778
830
959
1676
1840