配点: 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 信息中没有任何变化会导致两个圣诞老人处于相同的位置。
部分点
该问题分为多个子任务,如果您正确回答了该子任务中的所有测试用例,则视为您正确回答了该子任务。
提交的源代码的分数是您正确回答的子作业分数的总和。
- (2 点) M = 1,Q = 0.
- (6 点) M = 2,Q = 0.
- (14 点) N \leq 250,M \leq 250,Q = 0.
- (9 点) N \leq 3 \ 000,M \leq 3 \ 000,Q = 0.
- (9 点) Q = 0.
- (35 点) N \leq 40 \ 000, M \leq 40 \ 000, Q \leq 40 \ 000, T_i = 1.
- (19 点) N \leq 40 \ 000, M \leq 40 \ 000, Q \leq 40 \ 000.
- (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