Bear and Cavalry

题意翻译

题目描述:有n个人和n匹马,第i个人对应第i匹马。第i个人能力值wi,第i匹马能力值hi,第i个人骑第j匹马的总能力值为wi*hj,整个军队的总能力值为∑wihj(一个人只能骑一匹马,一匹马只能被一个人骑)。有一个要求:每个人都不能骑自己对应的马。让你制定骑马方案,使得整个军队的总能力值最大。现在有q个操作,每次给出a,b,交换a和b对应的马。每次操作后你都需要输出最大的总能力值。 输入:第一行是n和q,第二行是n个数wi,第三行是n个数hi 下面q行每行两个数a,b 输出q行,每行一个数表示最大的能力值 感谢@tlyangwj 提供翻译

题目描述

Would you want to fight against bears riding horses? Me neither. Limak is a grizzly bear. He is general of the dreadful army of Bearland. The most important part of an army is cavalry of course. Cavalry of Bearland consists of $ n $ warriors and $ n $ horses. $ i $ -th warrior has strength $ w_{i} $ and $ i $ -th horse has strength $ h_{i} $ . Warrior together with his horse is called a unit. Strength of a unit is equal to multiplied strengths of warrior and horse. Total strength of cavalry is equal to sum of strengths of all $ n $ units. Good assignment of warriors and horses makes cavalry truly powerful. Initially, $ i $ -th warrior has $ i $ -th horse. You are given $ q $ queries. In each query two warriors swap their horses with each other. General Limak must be ready for every possible situation. What if warriors weren't allowed to ride their own horses? After each query find the maximum possible strength of cavalry if we consider assignments of all warriors to all horses that no warrior is assigned to his own horse (it can be proven that for $ n>=2 $ there is always at least one correct assignment). Note that we can't leave a warrior without a horse.

输入输出格式

输入格式


The first line contains two space-separated integers, $ n $ and $ q $ ( $ 2<=n<=30\ 000 $ , $ 1<=q<=10\ 000 $ ). The second line contains $ n $ space-separated integers, $ w_{1},w_{2},...,w_{n} $ ( $ 1<=w_{i}<=10^{6} $ ) — strengths of warriors. The third line contains $ n $ space-separated integers, $ h_{1},h_{2},...,h_{n} $ ( $ 1<=h_{i}<=10^{6} $ ) — strengths of horses. Next $ q $ lines describe queries. $ i $ -th of them contains two space-separated integers $ a_{i} $ and $ b_{i} $ ( $ 1<=a_{i},b_{i}<=n $ , $ a_{i}≠b_{i} $ ), indices of warriors who swap their horses with each other.

输出格式


Print $ q $ lines with answers to queries. In $ i $ -th line print the maximum possible strength of cavalry after first $ i $ queries.

输入输出样例

输入样例 #1

4 2
1 10 100 1000
3 7 2 5
2 4
2 4

输出样例 #1

5732
7532

输入样例 #2

3 3
7 11 5
3 2 1
1 2
1 3
2 3

输出样例 #2

44
48
52

输入样例 #3

7 4
1 2 4 8 16 32 64
87 40 77 29 50 11 18
1 5
2 7
6 2
5 6

输出样例 #3

9315
9308
9315
9315

说明

Clarification for the first sample: Warriors: 1 10 100 1000Horses: 3 7 2 5 After first query situation looks like the following: Warriors: 1 10 100 1000Horses: 3 5 2 7 We can get $ 1·2+10·3+100·7+1000·5=5732 $ (note that no hussar takes his own horse in this assignment). After second query we get back to initial situation and optimal assignment is $ 1·2+10·3+100·5+1000·7=7532 $ . Clarification for the second sample. After first query: Warriors: 7 11 5Horses: 2 3 1 Optimal assignment is $ 7·1+11·2+5·3=44 $ . Then after second query $ 7·3+11·2+5·1=48 $ . Finally $ 7·2+11·3+5·1=52 $ .