Восстановление массива по суммам на отрезках

Дан неизвестный массив длины $n$ и набор условий: сумма на полуинтервале $[l, r)$ равна $x$. Проверить, непротиворечивы ли условия, и если да — предъявить подходящий массив.

Перейти к префиксным суммам

Первый ход — обычный для задач про суммы на отрезках. Пусть $S_i$ — сумма первых $i$ элементов, $S_0 = 0$. Тогда условие превращается в

$$S_r - S_l = x$$

Массив и набор префиксных сумм восстанавливаются друг из друга однозначно, так что задача равносильна.

Где здесь граф

Теперь видно: каждое условие связывает две величины и задаёт разность между ними. Это ребро.

Заведём $n+1$ вершину — по одной на границу $0, 1, \ldots, n$. Условие $(l, r, x)$ даёт ребро $l \to r$ веса $x$ и обратное $r \to l$ веса $-x$.

g[l].push_back({r,  x});
g[r].push_back({l, -x});

Пройдя по ребру, мы узнаём значение в его конце, зная значение в начале. Значит, обход из любой вершины расставляет значения по всей её компоненте связности.

Алгоритм

vector<long long> s(n + 1, NONE);
for (int start = 0; start <= n; start++) {
    if (s[start] != NONE) continue;
    s[start] = 0;                                  // свободная компонента: якорь произвольный
    vector<int> st{start};
    while (!st.empty()) {
        int v = st.back(); st.pop_back();
        for (auto [u, c] : g[v]) {
            if (s[u] == NONE) { s[u] = s[v] + c; st.push_back(u); }
            else if (s[u] != s[v] + c) return false;   // противоречие
        }
    }
}
for (int i = 0; i < n; i++) a[i] = s[i + 1] - s[i];

Проверено: на 200 000 наборов условий найденный массив всегда удовлетворял всем условиям, а обнаруженные противоречия подтвердились независимой проверкой потенциалов.

Три вещи, которые тут происходят

Противоречие — это цикл с ненулевой суммой весов. Придя в вершину вторым маршрутом и получив другое значение, мы обнаружили именно его.

Разные компоненты независимы. Если условия не связывают начало массива с концом, значения в разных компонентах можно выбирать произвольно. В коде якорь ставится в ноль — годится любое число.

Свобода внутри компоненты только одна. Зафиксировав одно значение, мы определяем все остальные в компоненте. Это в точности то, что даёт остовное дерево компоненты.

Вариант с ограничением на знак

Часто дополнительно требуют, чтобы все элементы были неотрицательны.

В компоненте, содержащей вершину 0, всё уже определено — проверяем и всё. А вот якоря свободных компонент можно двигать, и этим стоит воспользоваться: ставим значение так, чтобы разность с уже известным соседом слева была нулевой. Это соответствует нулевым элементам массива между известными кусками — минимально возможным при требовании неотрицательности.

Общий приём

Узнаётся так: условия связывают величины попарно и задают разность. Тогда величины — вершины, условия — рёбра, ответ — обход.

Так же решаются:

• «известны разности между парами чисел, восстановить числа»;
• «известно, кто кого тяжелее и на сколько, расставить веса»;
• система сравнений $x_i - x_j = c$ по модулю.

Если вместо равенств даны неравенства $x_i - x_j \le c$, приём тот же, но обход заменяется на Форда — Беллмана: решение существует тогда и только тогда, когда нет отрицательного цикла. Это называется системой разностных ограничений.