спасибо...

B. Динамика dp[x][y] — какое минимальное количество операций надо вставить так, чтобы у первого капитана были выполнены операции с нулевой по x — 1, а у второго — с нулевой по y — 1. Мы можем сделать либо x-ую операцию первого капитана, второй в это время пьет ром, либо y-ую операцию второго капитана, первый пьет ром, либо одновременно две операции.

Осталось научиться проверять, что сделанная операция не будет пересекать состояние другого капитана. Ну, давайте для каждого i и j насчитаем, пересекает ли i-я операция состояние на j-й префикс операций другого капитана. Это делается деревом отрезков с присвоением на отрезке. Дальше понятно, как отвечать на запросы.

Вот код, возможно, посмотрев на него, станет понятнее: http://pastebin.com/2zeWp4mQ

D. У меня код получил на самой олимпиаде 80, но вообще-то локально и на Codeforces он проходит все тесты.

У нас есть колесо. Будем называть все множество ребер, концом которых не является 0, колесом, а оставшиеся ребра — палками.

Заметим, что всегда существует минимальный остов, в котором не участвует максимальное ребро на колесе. Удалим его. Теперь колесо — отрезок.

Насчитаем динамику dp[v][2] — мы стоим на вершине v колеса, нолик или единичка при этом означают, соединена ли компонента связности, в которой сейчас вершина v, с нулевой вершиной. Переходы очевидны — соединяем вершину v с нулем или не соединяем, соединяем вершину v + 1 с нулем или не соединяем, соединяем вершину v + 1 с предыдущей или не соединяем. Получилось решение за O(Q * N).

А теперь надо просто запихнуть эту динамику в дерево отрезков. В каждой вершине дерева будем хранить dist[2][2] — длину минимального перехода из одного состояния в другое. Теперь, чтобы сделать апдейт значения на ребре, нужно просто сделать апдейт в дереве отрезков. Получилось решение за O(N log N).

Вот код: http://pastebin.com/fDECf5ZG