F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister
Problem 4908. -- [BeiJing2017]开车

4908: [BeiJing2017]开车

Time Limit: 30 Sec  Memory Limit: 256 MB
Submit: 161  Solved: 63
[Submit][Status][Discuss]

Description

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

Input

第一行一个正整数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之间。

Output

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

Sample Input

2
1 2
3 4
1
1 3

Sample Output

4
2
【样例解释】
一开始将第一辆车开到位置4,将第二辆车开到位置3,代价为 |4-1|+|3-2|=4。
修改后第一辆车的位置变成3,代价为 |3-3|+|4-2|=2。

HINT

Source

[Submit][Status][Discuss]

HOME Back