CF573D Bear and Cavalry

你想和骑着马的熊作战吗？我也不想。 Limak 是一只大灰熊。他是熊之国可怕军队的将军。这只军队中最重要的部分当然是骑兵了。 熊之国的骑兵共有 $n$ 位勇士和 $n$ 匹马。第 $i$ 位勇士的力量为 $w_{i}$，第 $i$ 匹马的力量为 $h_{i}$。勇士和他的马一起组成一个“单位”，该单位的力量为勇士的力量与马的力量的乘积。骑兵的总力量为所有 $n$ 个单位力量的总和。优秀的分配方式能让骑兵所向披靡。 起初，第 $i$ 位勇士拥有第 $i$ 匹马。你将得到 $q$ 次操作，每次操作有两位勇士交换他们的马。 Limak 将军必须为各种情况做好准备。假如勇士们被禁止骑自己的马呢？每次操作后，请计算在所有勇士与所有马进行匹配、且没有任何勇士分配给自己的马的所有方案中，骑兵可能达到的最大总力量是多少（可以证明当 $n \ge 2$ 时总有至少一种合法分配方式）。 注意，不能有勇士没有马。

第一行包含两个用空格分隔的整数 $n$ 和 $q$ ($2 \le n \le 30\ 000$，$1 \le q \le 10\ 000$)。 第二行包含 $n$ 个用空格分隔的整数 $w_{1}, w_{2}, ..., w_{n}$（$1 \le w_{i} \le 10^{6}$），表示勇士们的力量。 第三行包含 $n$ 个用空格分隔的整数 $h_{1}, h_{2}, ..., h_{n}$（$1 \le h_{i} \le 10^{6}$），表示马的力量。 接下来的 $q$ 行，每行描述一次操作。第 $i$ 行包含两个用空格分隔的整数 $a_{i}$ 和 $b_{i}$（$1 \le a_{i}, b_{i} \le n$，$a_{i} \ne b_{i}$），表示哪两位勇士交换了他们的马。

输出 $q$ 行，每行一个整数，第 $i$ 行表示第 $i$ 次操作后所有勇士与所有马匹配且无勇士骑到自己马上的最大总力量。

对第一个样例的说明： 勇士：1 10 100 1000 马：3 7 2 5 第一次操作后，情况如下： 勇士：1 10 100 1000 马：3 5 2 7 一种可能的分配方式为 $1·2+10·3+100·7+1000·5=5732$（注意此分配下没有勇士骑到自己的马）。 第二次操作后，回到初始状态，最优分配结果为 $1·2+10·3+100·5+1000·7=7532$。 对第二个样例的说明： 第一次操作后： 勇士：7 11 5 马：2 3 1 最优分配为 $7·1+11·2+5·3=44$。 第二次操作后为 $7·3+11·2+5·1=48$。 第三次操作后为 $7·2+11·3+5·1=52$。 由 ChatGPT 5 翻译