Это более сложная версия задачи H с запросами на изменение.
Лестер и Делберт работают в компании-производителе электроники. Сейчас они трудятся над микроплатой, которая должен соединять две независимые части большого суперкомпьютера.
Плата строится на основе макета в виде сетки. В макете \(n\) рядов и \(m\) столбцов, и на каждом пересечении ряда и столбца находится контакт. Также, на каждой из сторон макета расположены порты, которые можно подсоединять к ближайшему контакту. На левой и правой стороне находится по \(n\) портов, а на верхней и нижней — по \(m\) портов. Каждый из портов снаружи соединён с одной из частей суперкомпьютера, и раскрашен в красный либо синий цвет.
Порты можно соединять проводами внутри платы. Однако, есть несколько требований:
- Каждый провод должен соединять красный и синий порт, и каждый порт может быть соединён не более чем одним проводом.
- Каждый участок провода должен быть горизонтальным либо вертикальным, и повороты возможно только в одном из контактов.
- Чтобы избежать интерференции, провода не должны иметь общих частей ненулевой длины (однако, они могут проходить через общие контакты). Кроме того, провод не может покрывать один участок ненулевой длины дважды.
Пропускной способностью платы называется наибольшее количество соединений между красными и синими портами, которого можно достичь, соблюдая условия выше. Например, плата, изображенная выше, имеет пропускную способность \(7\), и один из способов построить семь соединений изображён ниже.
До этого места условия обеих версий задачи совпадают. Различия начинаются ниже.
Как это часто бывает, спецификации проекта в ходе разработки часто меняются, поэтому цвета всех портов ещё не установлены окончательно. Приходит \(q\) модификаций, каждая из которых выглядит так: «цвета всех портов на непрерывном отрезке вдоль одной из сторон меняются на противоположные (красные на синий, синие на красный)». Предыдущие модификации не отменяются перед тем, как происходит следующая.
Чтобы оценить критичность изменений, Лестер и Делберт должны узнать пропускную способность платы после каждой модификации. Помогите им сделать это эффективно.