AT_pakencamp_2019_day3_g プレゼント配り2

E869120 君在「AtCoder 圣诞老人事务局」里工作，每年负责让圣诞老人高效地递送礼物。 今年，E869120 君的任务是收集「AtCoder 街」上的圣诞老人和房子的位置信息，从而提高礼物配送的效率。 AtCoder 街是一条从西到东的直路，长达 $1,000,000,000$ 米。E869120 君最初获取的相关信息如下： - 街道上有 $N$ 栋房子，编号为 $1$ 到 $N$。编号为 $i$ 的房子位于从西端起 $A_i$ 米处。 - 街道上有 $M$ 位圣诞老人，编号为 $1$ 到 $M$。编号为 $i$ 的圣诞老人位于从西端起 $B_i$ 米处。 但在 AtCoder 街，房子可能搬迁，圣诞老人也可能移动。因此，在圣诞节前，可能会有 $Q$ 次信息更新。每次更新如下： - 如果 $T_i = 1$，则编号为 $C_i$ 的房子位置被更改为距离西端 $D_i$ 米处。 - 如果 $T_i = 2$，则编号为 $C_i$ 的圣诞老人位置被更改为距离西端 $D_i$ 米处。 请在每次信息更新后，即 $i = 0, 1, 2, \ldots, Q$，回答这个问题： - 为了所有房子都能收到礼物，所有 $M$ 位圣诞老人一共需要移动多少米？ - 假设所有圣诞老人永远都有足够多的礼物。 - 圣诞老人必须亲自到达房子所在位置进行配送，无法远程投掷礼物。送完礼物后，圣诞老人无需返回原位置。 注意，「第 $0$ 次更新后的信息」指的是E869120 君首次收到的信息。

输入从标准输入以如下格式给出： > $N\ A_1\ A_2\ A_3\ \ldots\ A_N\ M\ B_1\ B_2\ B_3\ \ldots\ B_M\ Q\ T_1\ C_1\ D_1\ T_2\ C_2\ D_2\ T_3\ C_3\ D_3\ \ldots\ T_Q\ C_Q\ D_Q$

输出共 $Q+1$ 行，每行表示在第 $i-1$ 次更新后，圣诞老人需要移动的最小总距离。

### 约束条件 - $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$ 是奇数。 - 不会出现两个房子或两个圣诞老人处于相同位置的情况。 ### 部分得分 这道题拥有多个子任务。代码通过所有子任务的所有测试用例时，该子任务视为正确。提交代码的得分为所有通过的子任务得分之和。 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 分) 没有额外限制。 ### 示例解释 1 如果圣诞老人按照以下方式移动，总移动距离为 $69$ 米，这是最小值： - 圣诞老人 1 移动到房子 1，送出礼物，此时移动距离为 $13$ 米。 - 然后移动到房子 2，送出礼物，此时移动距离为 $19$ 米。 - 接着移动到房子 3，送出礼物，此时移动距离为 $37$ 米。 - 再移动到房子 4，送出礼物，此时移动距离为 $51$ 米。 - 最后移动到房子 5，送出礼物，此时总移动距离为 $69$ 米。 ### 示例解��� 2 该例满足题目小任务 2 的限制。注意，小任务 2 不包括输入示例 1 中的 $M = 1$ 的情况。 ### 示例解释 3 该例满足题目小任务 3、4、5 的限制。 **本翻译由 AI 自动生成**