#P3992. [BJOI2017] 开车

    ID: 4988 远端评测题 1500ms 250MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>2017各省省选北京O2优化排序前缀和块状链表,块状数组,分块

[BJOI2017] 开车

题目描述

nn 辆车,分别在 a1,a2,,ana_1, a_2, \ldots , a_n 位置和 nn 个加油站,分别在 b1,b2,,bnb_1, b_2, \ldots ,b_n 位置。

每个加油站只能支持一辆车的加油,所以你要把这些车开到不同的加油站加油。一个车从 xx 位置开到 yy 位置的代价为 xy|x-y|,问如何安排车辆,使得代价之和最小。

同时你有 qq 个操作,每次操作会修改第 ii 辆车的位置到 xx,你要回答每次修改操作之后最优安排方案的总代价。

输入格式

第一行一个正整数 nn

接下来一行 nn 个整数 a1,a2,,ana_1, a_2,\ldots,a_n

接下来一行 nn 个整数 b1,b2,,bnb_1, b_2,\ldots,b_n

接下来一行一个正整数 qq,表示操作的个数。

接下来 qq 行,每行有两个整数 ii1in1\leq i\leq n)和 xx,表示将i这辆车开到 xx 位置的操作。

所有的车和加油站的范围一直在 0010910^9 之间。

输出格式

q+1q+1 行,第一行表示一开始的最优代价。

接下来 qq 行,第 ii 行表示操作 ii 之后的最优代价。

2
1 2
3 4
1
1 3

4
2

提示

【样例解释】

一开始将第一辆车开到位置 44,将第二辆车开到位置 33,代价为 41+32=4|4-1|+|3-2|=4

修改后第一辆车的位置变成 33,代价为 33+42=2|3-3|+|4-2|=2

测试点 数据范围
11 n103n\leq 10^3q=0q=0
22 n103n\leq 10^3q103q\leq 10^3
33 n104n\leq 10^4q104q\leq 10^4
44 n5×104n\leq 5\times 10^4q=0q=0
565\sim 6 n3×104n\leq 3\times 10^4q3×104q\leq 3\times 10^4
7107\sim 10 n5×104n\leq 5\times 10^4q5×104q\leq 5\times 10^4

对于 100%100\% 的数据,1n5×1041\leq n\leq 5\times 10^40q5×1040\leq q\leq 5\times 10^4