4908. [BeiJing2017]开车
#4908. [BeiJing2017]开车
题目描述
你有n辆车，分别a1, a2, ..., an位置和n个加油站，分别在b1, b2, ... ,bn 。每个加油站只能支持一辆车的加
油，所以你要把这些车开到不同的加油站加油。一个车从x位置开到y位置的代价为 |x-y| ，问如何安排车辆，使
得代价之和最小。同时你有q个操作，每次操作会修改第i辆车的位置到x，你要回答每次修改操作之后最优安排方
案的总代价。
输入格式
第一行一个正整数n，接下来一行n个整数a1, a2, ...,an，接下来一行n个整数b1, b2,... ,bn。
接下来一行一个正整数q，表示操作的个数。
接下来q行，每行有两个整数i(1 ≤ i ≤ n)和x，表示将i这辆车开到x位置的操作。
1 ≤ n, q ≤ 5 * 10^4，所有的车和加油站的范围一直在0到10^9之间。
输出格式
共q+1行，第一行表示一开始的最优代价。接下来q行，第i行表示操作i之后的最优代价。
样例
样例输入
2
1 2
3 4
1
1 3
样例输出
4
2
【样例解释】
一开始将第一辆车开到位置4，将第二辆车开到位置3，代价为 |4-1|+|3-2|=4。
修改后第一辆车的位置变成3，代价为 |3-3|+|4-2|=2。