Олимпиадный тренинг

Задача . D. Мишка и кавалерия


Задача

Темы: дп разделяй и властвуй Структуры данных *3000

Вы бы хотели поучаствовать в конном сражении с мишками? Я — не очень.

Лимак — мишка гризли. Он генерал ужасной армии Мишляндии. Как вы знаете, самая важная часть армии — это, конечно, кавалерия.

Кавалерия Мишляндии состоит из n воинов и n лошадей. У i-го воина сила равна wi, а у i-й лошади сила равна hi. Воин со своей лошадью называется юнитом. Сила юнита равна произведению сил воина и лошади. Общая сила кавалерии равна сумме сил всех n юнитов. Правильное распределение воинов и лошадей делает кавалерию по-настоящему мощной.

Изначально i-му воину принадлежит i-я лошадь. Вам дано q запросов. После каждого запроса два воина меняются друг с другом лошадьми.

Генерал Лимак должен быть готов к любой возможной ситуации. Что, если бы воинам было запрещено скакать на своих лошадях? Поэтому после каждого запроса вам требуется найти максимальную возможную силу кавалерии, если мы рассматриваем только такие сопоставления воинов лошадям, что ни одному воину не достается его собственная лошадь (можно доказать, что для n ≥ 2 всегда есть не менее одного корректного распределения).

Входные данные

В первой строке содержатся два целых числа через пробел, n и q (2 ≤ n ≤ 30 000, 1 ≤ q ≤ 10 000).

Во второй строке содержится n целых чисел через пробел, w1, w2, ..., wn (1 ≤ wi ≤ 106) — силы воинов.

В третьей строке содержится n целых чисел через пробел, h1, h2, ..., hn (1 ≤ hi ≤ 106) — силы лошадей.

Следующие q строк описывают запросы. i-я из них содержит два целых числа через пробел, ai и bi (1 ≤ ai, bi ≤ n, ai ≠ bi), индексы воинов, которые меняются лошадьми друг с другом.

Выходные данные

Выведите 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.


Примеры
№Входные данныеВыходные данные
1 4 2
1 10 100 1000
3 7 2 5
2 4
2 4 
5732
7532
2 3 3
7 11 5
3 2 1
1 2
1 3
2 3 
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 
9315
9308
9315
9315

time 3000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет