[BJOI2017]开车

题目描述

你有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之后的最优代价。

输入输出样例

输入样例 #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。 ```plain 测试点 数据范围 1 n<=1000,q=0 2 n<=1000,q<=1000 3 n<=10000,q<=10000 4 n<=50000,q=0 5~6 n<=30000,q<=30000 7~10 n<=50000,q<=50000 ```