[BJOI2017]开车

题目描述

有 $n$ 辆车,分别在 $a_1, a_2, \ldots , a_n$ 位置和 $n$ 个加油站,分别在 $b_1, b_2, \ldots ,b_n$ 位置。 每个加油站只能支持一辆车的加油,所以你要把这些车开到不同的加油站加油。一个车从 $x$ 位置开到 $y$ 位置的代价为 $|x-y|$,问如何安排车辆,使得代价之和最小。 同时你有 $q$ 个操作,每次操作会修改第 $i$ 辆车的位置到 $x$,你要回答每次修改操作之后最优安排方案的总代价。

输入输出格式

输入格式


第一行一个正整数 $n$。 接下来一行 $n$ 个整数 $a_1, a_2,\ldots,a_n$。 接下来一行 $n$ 个整数 $b_1, b_2,\ldots,b_n$。 接下来一行一个正整数 $q$,表示操作的个数。 接下来 $q$ 行,每行有两个整数 $i$($1\leq i\leq n$)和 $x$,表示将i这辆车开到 $x$ 位置的操作。 所有的车和加油站的范围一直在 $0$ 到 $10^9$ 之间。

输出格式


共 $q+1$ 行,第一行表示一开始的最优代价。 接下来 $q$ 行,第 $i$ 行表示操作 $i$ 之后的最优代价。

输入输出样例

输入样例 #1

2
1 2
3 4
1
1 3

输出样例 #1

4
2

说明

【样例解释】 一开始将第一辆车开到位置 $4$,将第二辆车开到位置 $3$,代价为 $|4-1|+|3-2|=4$。 修改后第一辆车的位置变成 $3$,代价为 $|3-3|+|4-2|=2$。 |测试点|数据范围| |:-:|:-:| |$1$| $n\leq 10^3$,$q=0$| |$2$| $n\leq 10^3$,$q\leq 10^3$| |$3$| $n\leq 10^4$,$q\leq 10^4$| |$4$| $n\leq 5\times 10^4$,$q=0$| |$5\sim 6$| $n\leq 3\times 10^4$,$q\leq 3\times 10^4$| |$7\sim 10$| $n\leq 5\times 10^4$,$q\leq 5\times 10^4$| 对于 $100\%$ 的数据,$1\leq n\leq 5\times 10^4$,$0\leq q\leq 5\times 10^4$。