P3992 [BJOI2017] Driving

There are $n$ cars located at positions $a_1, a_2, \ldots, a_n$, and $n$ gas stations located at positions $b_1, b_2, \ldots, b_n$. Each gas station can serve at most one car, so you must drive the cars to distinct gas stations. The cost for a car to drive from position $x$ to position $y$ is $|x - y|$. Find an assignment that minimizes the sum of costs. You are also given $q$ operations. In each operation, the position of the $i$-th car is updated to $x$. After each update, you need to output the minimal total cost of an optimal assignment.

The first line contains a positive integer $n$. The second line contains $n$ integers $a_1, a_2, \ldots, a_n$. The third line contains $n$ integers $b_1, b_2, \ldots, b_n$. The fourth line contains a positive integer $q$, the number of operations. Each of the next $q$ lines contains two integers $i$ ($1 \le i \le n$) and $x$, indicating that the position of car $i$ is updated to $x$. All car and gas station positions are always within $0$ to $10^9$.

Output $q + 1$ lines. The first line is the minimal total cost before any operations. Then output $q$ lines, where the $i$-th line is the minimal total cost after operation $i$.

Sample explanation: Initially, drive the first car to position $4$ and the second car to position $3$, with a total cost of $|4 - 1| + |3 - 2| = 4$. After the update, the first car’s position becomes $3$, and the total cost is $|3 - 3| + |4 - 2| = 2$. | Test points | Constraints | |:-:|:-:| | $1$ | $n \le 10^3$, $q = 0$ | | $2$ | $n \le 10^3$, $q \le 10^3$ | | $3$ | $n \le 10^4$, $q \le 10^4$ | | $4$ | $n \le 5 \times 10^4$, $q = 0$ | | $5 \sim 6$ | $n \le 3 \times 10^4$, $q \le 3 \times 10^4$ | | $7 \sim 10$ | $n \le 5 \times 10^4$, $q \le 5 \times 10^4$ | For $100\%$ of the testdata, $1 \le n \le 5 \times 10^4$, $0 \le q \le 5 \times 10^4$. Translated by ChatGPT 5