flow/dynamic_mcf_on_line.hpp

• View this file on GitHub
• Last update: 2026-10-15 19:54:56+09:00
• Include: #include "flow/dynamic_mcf_on_line.hpp"
• Link: https://github.com/maspypy/library/blob/main/flow/dynamic_mcf_on_line.hpp

Depends on

• alg/monoid/add.hpp
• ds/segtree/lazy_segtree.hpp
• ds/segtree/segtree.hpp

Code

// Source: https://github.com/maspypy/library/blob/main/flow/dynamic_mcf_on_line.hpp
#include "alg/monoid/add.hpp"
#include "ds/segtree/lazy_segtree.hpp"
#include "ds/segtree/segtree.hpp"

// O(|cap| log N) per operation
template <typename T>
struct Dynamic_MCF_on_Line {
  int N;
  T ANS;

  using P = pair<T, int>;
  struct Mono {
    struct X {
      P from, to;
    };
    using value_type = X;
    static X op(const X& a, const X& b) {
      return {min(a.from, b.from), min(a.to, b.to)};
    }
    static constexpr X id() { return {{infty<T>, -1}, {infty<T>, -1}}; }
    static constexpr bool commute = true;
  };

  vc<map<T, int>> S_remain, S_used;
  vc<map<T, int>> T_remain, T_used;

  SegTree<Mono> seg_terminal;

  struct Mono_Line {
    struct X {
      int left, right;
    };
    using value_type = X;
    static X op(const X& a, const X& b) {
      return {min(a.left, b.left), min(a.right, b.right)};
    }
    static constexpr X id() { return {infty<int>, infty<int>}; }
    static constexpr bool commute = true;
  };

  struct AM {
    using Monoid_X = Mono_Line;
    using Monoid_A = Monoid_Add<int>;
    using X = typename Monoid_X::value_type;
    using A = typename Monoid_A::value_type;
    static X act(X x, const A& a, const ll&) {
      x.left += a, x.right -= a;
      return x;
    }
  };

  using X = typename Mono_Line::value_type;
  Lazy_SegTree<AM> seg_flow;

  Dynamic_MCF_on_Line(int N, const vc<int>& right_cap, const vc<int>& left_cap)
      : N(N),
        ANS(0),
        S_remain(N),
        S_used(N),
        T_remain(N),
        T_used(N),
        seg_terminal(N) {
    assert(N > 0);
    assert(len(right_cap) == N - 1);
    assert(len(left_cap) == N - 1);
    FOR(i, N - 1) {
      assert(right_cap[i] >= 0);
      assert(left_cap[i] >= 0);
    }
    seg_flow.build(
        N - 1, [&](int i) -> X { return {left_cap[i], right_cap[i]}; });
  }

  void add_source(int v, T cost, int cap = 1) {
    assert(0 <= v && v < N);
    assert(cap >= 0);
    mp_add(S_remain[v], cost, cap);
    update_terminal(v);

    FOR(cap) {
      auto [l, r] = reachable_from(v);
      // v -> ... -> w -> hub
      auto [c, w] = seg_terminal.prod(l, r + 1).to;
      if (w == -1 || cost + c >= 0) break;
      move_mp(S_remain[v], S_used[v], cost, 1);
      ANS += cost;
      update_terminal(v);
      push_line(v, w, 1);
      push_to_hub(w, c);
    }
  }

  void add_sink(int v, T cost, int cap = 1) {
    assert(0 <= v && v < N);
    assert(cap >= 0);

    mp_add(T_remain[v], cost, cap);
    update_terminal(v);

    FOR(cap) {
      auto [l, r] = reachable_to(v);
      // hub -> w -> ... -> v
      auto [c, w] = seg_terminal.prod(l, r + 1).from;
      if (w == -1 || c + cost >= 0) break;
      push_from_hub(w, c);
      push_line(w, v, 1);
      move_mp(T_remain[v], T_used[v], cost, 1);
      ANS += cost;
      update_terminal(v);
    }
  }

  void rm_source(int v, T cost, int cap = 1) {
    assert(0 <= v && v < N);
    assert(cap >= 0);
    int a = mp_count(S_remain[v], cost);
    int b = mp_count(S_used[v], cost);
    assert(a + b >= cap);

    int k = min(cap, a);
    mp_sub(S_remain[v], cost, k);
    cap -= k;
    update_terminal(v);

    FOR(cap) {
      mp_sub(S_used[v], cost, 1);
      ANS -= cost;
      update_terminal(v);
      auto [l, r] = reachable_to(v);
      auto [c, w] = seg_terminal.prod(l, r + 1).from;
      assert(w != -1);
      push_from_hub(w, c);
      push_line(w, v, 1);
    }
  }

  void rm_sink(int v, T cost, int cap = 1) {
    assert(0 <= v && v < N);
    assert(cap >= 0);
    int a = mp_count(T_remain[v], cost);
    int b = mp_count(T_used[v], cost);
    assert(a + b >= cap);
    int k = min(cap, a);
    mp_sub(T_remain[v], cost, k);
    cap -= k;
    update_terminal(v);
    FOR(cap) {
      mp_sub(T_used[v], cost, 1);
      ANS -= cost;
      update_terminal(v);
      auto [l, r] = reachable_from(v);
      auto [c, w] = seg_terminal.prod(l, r + 1).to;
      assert(w != -1);
      push_line(v, w, 1);
      push_to_hub(w, c);
    }
  }

 private:
  static int mp_count(const map<T, int>& mp, const T& x) {
    auto it = mp.find(x);
    return (it == mp.end() ? 0 : it->second);
  }

  static void mp_add(map<T, int>& mp, const T& x, int k) {
    assert(k >= 0);
    if (k == 0) return;
    mp[x] += k;
  }

  static void mp_sub(map<T, int>& mp, const T& x, int k) {
    assert(k >= 0);
    if (k == 0) return;
    auto it = mp.find(x);
    assert(it != mp.end() && it->second >= k);
    it->second -= k;
    if (it->second == 0) mp.erase(it);
  }

  static void move_mp(map<T, int>& A, map<T, int>& B, const T& x, int k) {
    mp_sub(A, x, k), mp_add(B, x, k);
  }

  void update_terminal(int v) {
    auto x = Mono::id();
    if (!S_remain[v].empty()) chmin(x.from, P{S_remain[v].begin()->first, v});
    if (!T_used[v].empty()) chmin(x.from, P{-T_used[v].rbegin()->first, v});
    if (!T_remain[v].empty()) chmin(x.to, P{T_remain[v].begin()->first, v});
    if (!S_used[v].empty()) chmin(x.to, P{-S_used[v].rbegin()->first, v});

    seg_terminal.set(v, x);
  }

  void push_from_hub(int v, T cost) {
    if (!S_remain[v].empty() && S_remain[v].begin()->first == cost) {
      move_mp(S_remain[v], S_used[v], cost, 1);
      ANS += cost;
      update_terminal(v);
      return;
    }

    assert(!T_used[v].empty());
    T c = T_used[v].rbegin()->first;
    assert(-c == cost);

    move_mp(T_used[v], T_remain[v], c, 1);
    ANS -= c;
    update_terminal(v);
  }

  void push_to_hub(int v, T cost) {
    if (!T_remain[v].empty() && T_remain[v].begin()->first == cost) {
      move_mp(T_remain[v], T_used[v], cost, 1);
      ANS += cost;
      update_terminal(v);
      return;
    }

    assert(!S_used[v].empty());
    T c = S_used[v].rbegin()->first;
    assert(-c == cost);

    move_mp(S_used[v], S_remain[v], c, 1);
    ANS -= c;
    update_terminal(v);
  }

  // v から到達可能な vertex interval [l, r]
  pair<int, int> reachable_from(int v) {
    int l =
        seg_flow.min_left([&](const X& x) -> bool { return x.left > 0; }, v);
    int r =
        seg_flow.max_right([&](const X& x) -> bool { return x.right > 0; }, v);
    return {l, r};
  }

  // v に到達可能な vertex interval [l, r]
  pair<int, int> reachable_to(int v) {
    int l =
        seg_flow.min_left([&](const X& x) -> bool { return x.right > 0; }, v);
    int r =
        seg_flow.max_right([&](const X& x) -> bool { return x.left > 0; }, v);
    return {l, r};
  }

  void push_line(int s, int t, int f) {
    assert(f >= 0);
    if (s == t || f == 0) return;

    if (s < t) {
      assert(seg_flow.prod(s, t).right >= f);
      seg_flow.apply(s, t, +f);
    } else {
      assert(seg_flow.prod(t, s).left >= f);
      seg_flow.apply(t, s, -f);
    }
  }
};

#line 1 "flow/dynamic_mcf_on_line.hpp"
// Source: https://github.com/maspypy/library/blob/main/flow/dynamic_mcf_on_line.hpp
#line 1 "alg/monoid/add.hpp"
// Source: https://github.com/maspypy/library/blob/main/alg/monoid/add.hpp

template <typename E>
struct Monoid_Add {
  using X = E;
  using value_type = X;
  static constexpr X op(const X &x, const X &y) noexcept { return x + y; }
  static constexpr X inverse(const X &x) noexcept { return -x; }
  static constexpr X power(const X &x, ll n) noexcept { return X(n) * x; }
  static constexpr X id() { return X(0); }
  static constexpr bool commute = true;
};
#line 1 "ds/segtree/lazy_segtree.hpp"
// Source: https://github.com/maspypy/library/blob/main/ds/segtree/lazy_segtree.hpp

template <typename ActedMonoid>
struct Lazy_SegTree {
  using AM = ActedMonoid;
  using MX = typename AM::Monoid_X;
  using MA = typename AM::Monoid_A;
  using X = typename MX::value_type;
  using A = typename MA::value_type;
  int n, log, size;
  vc<X> dat;
  vc<A> laz;
  vc<bool> has_laz;

  Lazy_SegTree() {}
  Lazy_SegTree(int n) { build(n); }
  template <typename F>
  Lazy_SegTree(int n, F f) {
    build(n, f);
  }
  Lazy_SegTree(const vc<X>& v) { build(v); }

  void build(int m) {
    build(m, [](int i) -> X { return MX::id(); });
  }
  void build(const vc<X>& v) {
    build(len(v), [&](int i) -> X { return v[i]; });
  }
  template <typename F>
  void build(int m, F f) {
    n = m, log = 0;
    while ((1 << log) < n) ++log;
    size = 1 << log;
    dat.assign(size << 1, MX::id());
    laz.assign(size, MA::id());
    has_laz.assign(size, false);
    FOR(i, n) dat[size + i] = f(i);
    FOR_R(i, 1, size) update(i);
  }

  void update(int k) { dat[k] = MX::op(dat[2 * k], dat[2 * k + 1]); }
  void set(int p, X x) {
    assert(0 <= p && p < n);
    p += size;
    for (int i = log; i >= 1; i--) push(p >> i);
    dat[p] = x;
    for (int i = 1; i <= log; i++) update(p >> i);
  }
  void multiply(int p, const X& x) {
    assert(0 <= p && p < n);
    p += size;
    for (int i = log; i >= 1; i--) push(p >> i);
    dat[p] = MX::op(dat[p], x);
    for (int i = 1; i <= log; i++) update(p >> i);
  }

  X get(int p) {
    assert(0 <= p && p < n);
    p += size;
    for (int i = log; i >= 1; i--) push(p >> i);
    return dat[p];
  }

  vc<X> get_all() {
    FOR(k, 1, size) { push(k); }
    return {dat.begin() + size, dat.begin() + size + n};
  }

  X prod(int l, int r) {
    assert(0 <= l && l <= r && r <= n);
    if (l == r) return MX::id();
    l += size, r += size;
    for (int i = log; i >= 1; i--) {
      if (((l >> i) << i) != l) push(l >> i);
      if (((r >> i) << i) != r) push((r - 1) >> i);
    }
    X xl = MX::id(), xr = MX::id();
    while (l < r) {
      if (l & 1) xl = MX::op(xl, dat[l++]);
      if (r & 1) xr = MX::op(dat[--r], xr);
      l >>= 1, r >>= 1;
    }
    return MX::op(xl, xr);
  }

  X prod_all() { return dat[1]; }

  void apply(int l, int r, A a) {
    assert(0 <= l && l <= r && r <= n);
    if (l == r) return;
    l += size, r += size;
    for (int i = log; i >= 1; i--) {
      if (((l >> i) << i) != l) push(l >> i);
      if (((r >> i) << i) != r) push((r - 1) >> i);
    }
    int l2 = l, r2 = r;
    while (l < r) {
      if (l & 1) apply_at(l++, a);
      if (r & 1) apply_at(--r, a);
      l >>= 1, r >>= 1;
    }
    l = l2, r = r2;
    for (int i = 1; i <= log; i++) {
      if (((l >> i) << i) != l) update(l >> i);
      if (((r >> i) << i) != r) update((r - 1) >> i);
    }
  }

  template <typename F>
  int max_right(const F check, int l) {
    assert(0 <= l && l <= n);
    assert(check(MX::id()));
    if (l == n) return n;
    l += size;
    for (int i = log; i >= 1; i--) push(l >> i);
    X sm = MX::id();
    do {
      while (l % 2 == 0) l >>= 1;
      if (!check(MX::op(sm, dat[l]))) {
        while (l < size) {
          push(l);
          l = (2 * l);
          if (check(MX::op(sm, dat[l]))) {
            sm = MX::op(sm, dat[l++]);
          }
        }
        return l - size;
      }
      sm = MX::op(sm, dat[l++]);
    } while ((l & -l) != l);
    return n;
  }

  template <typename F>
  int min_left(const F check, int r) {
    assert(0 <= r && r <= n);
    assert(check(MX::id()));
    if (r == 0) return 0;
    r += size;
    for (int i = log; i >= 1; i--) push((r - 1) >> i);
    X sm = MX::id();
    do {
      r--;
      while (r > 1 && (r % 2)) r >>= 1;
      if (!check(MX::op(dat[r], sm))) {
        while (r < size) {
          push(r);
          r = (2 * r + 1);
          if (check(MX::op(dat[r], sm))) {
            sm = MX::op(dat[r--], sm);
          }
        }
        return r + 1 - size;
      }
      sm = MX::op(dat[r], sm);
    } while ((r & -r) != r);
    return 0;
  }

  // l <= i xor (xor_val) < r となる i 全体に apply
  void apply_xor_range(int l, int r, int xor_val, A a) {
    assert(!(n & (n - 1)));
    assert(0 <= xor_val && xor_val < n);
    assert(0 <= l && l <= r && r <= n);

    auto dfs = [&](auto& dfs, int idx, int seg_l, int seg_r) -> void {
      if (l <= seg_l && seg_r <= r) {
        return apply_at(idx, a);
      }
      if (r <= seg_l || seg_r <= l) return;
      push(idx);
      int seg_m = (seg_l + seg_r) / 2;
      int bit = (seg_r - seg_l) / 2;
      int left = 2 * idx + 0, right = 2 * idx + 1;
      if (xor_val & bit) swap(left, right);
      dfs(dfs, left, seg_l, seg_m);
      dfs(dfs, right, seg_m, seg_r);
      update(idx);
    };
    dfs(dfs, 1, 0, n);
  }

 private:
  void apply_at(int k, A a) {
    ll sz = 1 << (log - topbit(k));
    dat[k] = AM::act(dat[k], a, sz);
    if (k < size) has_laz[k] = 1, laz[k] = MA::op(laz[k], a);
  }
  void push(int k) {
    if (!has_laz[k]) return;
    has_laz[k] = 0;
    apply_at(2 * k, laz[k]), apply_at(2 * k + 1, laz[k]);
    laz[k] = MA::id();
  }
};
#line 1 "ds/segtree/segtree.hpp"
// Source: https://github.com/maspypy/library/blob/main/ds/segtree/segtree.hpp

template <class Monoid>
struct SegTree {
  using MX = Monoid;
  using X = typename MX::value_type;
  using value_type = X;
  vc<X> dat;
  int n, log, size;

  SegTree() {}
  SegTree(int n) { build(n); }
  template <typename F>
  SegTree(int n, F f) {
    build(n, f);
  }
  SegTree(const vc<X>& v) { build(v); }

  void build(int m) {
    build(m, [](int i) -> X { return MX::id(); });
  }
  void build(const vc<X>& v) {
    build(len(v), [&](int i) -> X { return v[i]; });
  }
  template <typename F>
  void build(int m, F f) {
    n = m, log = 0;
    while ((1 << log) < n) ++log;
    size = 1 << log;
    dat.assign(size << 1, MX::id());
    FOR(i, n) dat[size + i] = f(i);
    FOR_R(i, 1, size) update(i);
  }

  X get(int i) const { return dat[size + i]; }
  vc<X> get_all() const { return {dat.begin() + size, dat.begin() + size + n}; }

  void update(int i) { dat[i] = Monoid::op(dat[2 * i], dat[2 * i + 1]); }
  void set(int i, const X& x) {
    assert(0 <= i && i < n);
    dat[i += size] = x;
    while (i >>= 1) update(i);
  }

  void multiply(int i, const X& x) {
    assert(0 <= i && i < n);
    i += size;
    dat[i] = Monoid::op(dat[i], x);
    while (i >>= 1) update(i);
  }

  X prod(int L, int R) const {
    assert(0 <= L && L <= R && R <= n);
    X vl = Monoid::id(), vr = Monoid::id();
    L += size, R += size;
    while (L < R) {
      if (L & 1) vl = Monoid::op(vl, dat[L++]);
      if (R & 1) vr = Monoid::op(dat[--R], vr);
      L >>= 1, R >>= 1;
    }
    return Monoid::op(vl, vr);
  }

  vc<int> prod_ids(int L, int R) const {
    assert(0 <= L && L <= R && R <= n);
    vc<int> I, J;
    L += size, R += size;
    while (L < R) {
      if (L & 1) I.eb(L++);
      if (R & 1) J.eb(--R);
      L >>= 1, R >>= 1;
    }
    reverse(all(J));
    concat(I, J);
    return I;
  }

  X prod_all() const { return dat[1]; }

  template <class F>
  int max_right(F check, int L) const {
    assert(0 <= L && L <= n && check(Monoid::id()));
    if (L == n) return n;
    L += size;
    X sm = Monoid::id();
    do {
      while (L % 2 == 0) L >>= 1;
      if (!check(Monoid::op(sm, dat[L]))) {
        while (L < size) {
          L = 2 * L;
          if (check(Monoid::op(sm, dat[L]))) {
            sm = Monoid::op(sm, dat[L++]);
          }
        }
        return L - size;
      }
      sm = Monoid::op(sm, dat[L++]);
    } while ((L & -L) != L);
    return n;
  }

  template <class F>
  int min_left(F check, int R) const {
    assert(0 <= R && R <= n && check(Monoid::id()));
    if (R == 0) return 0;
    R += size;
    X sm = Monoid::id();
    do {
      --R;
      while (R > 1 && (R % 2)) R >>= 1;
      if (!check(Monoid::op(dat[R], sm))) {
        while (R < size) {
          R = 2 * R + 1;
          if (check(Monoid::op(dat[R], sm))) {
            sm = Monoid::op(dat[R--], sm);
          }
        }
        return R + 1 - size;
      }
      sm = Monoid::op(dat[R], sm);
    } while ((R & -R) != R);
    return 0;
  }

  // prod_{l<=i<r} A[i xor x]
  X xor_prod(int l, int r, int xor_val) const {
    static_assert(Monoid::commute);
    X x = Monoid::id();
    for (int k = 0; k < log + 1; ++k) {
      if (l >= r) break;
      if (l & 1) {
        x = Monoid::op(x, dat[(size >> k) + ((l++) ^ xor_val)]);
      }
      if (r & 1) {
        x = Monoid::op(x, dat[(size >> k) + ((--r) ^ xor_val)]);
      }
      l /= 2, r /= 2, xor_val /= 2;
    }
    return x;
  }

  // f(i), i in I
  // 近いインデックスを大量に同時更新したいときに効率が良くなるという狙い
  template <typename F>
  void set_many_sorted(vc<int> I, F f) {
    if (I.empty()) return;

    FOR(k, len(I)) {
      assert(0 <= I[k] && I[k] < n);
      if (k) assert(I[k - 1] < I[k]);
    }

    FOR(k, len(I)) {
      int i = I[k];
      dat[size + i] = f(i);
      I[k] += size;
    }

    int m = len(I);
    while (I[0] > 1) {
      int nxt = 0;
      int last = -1;
      FOR(k, m) {
        int p = I[k] >> 1;
        if (p == last) continue;
        update(p);
        I[nxt++] = p;
        last = p;
      }
      m = nxt;
    }
  }
};
#line 5 "flow/dynamic_mcf_on_line.hpp"

// O(|cap| log N) per operation
template <typename T>
struct Dynamic_MCF_on_Line {
  int N;
  T ANS;

  using P = pair<T, int>;
  struct Mono {
    struct X {
      P from, to;
    };
    using value_type = X;
    static X op(const X& a, const X& b) {
      return {min(a.from, b.from), min(a.to, b.to)};
    }
    static constexpr X id() { return {{infty<T>, -1}, {infty<T>, -1}}; }
    static constexpr bool commute = true;
  };

  vc<map<T, int>> S_remain, S_used;
  vc<map<T, int>> T_remain, T_used;

  SegTree<Mono> seg_terminal;

  struct Mono_Line {
    struct X {
      int left, right;
    };
    using value_type = X;
    static X op(const X& a, const X& b) {
      return {min(a.left, b.left), min(a.right, b.right)};
    }
    static constexpr X id() { return {infty<int>, infty<int>}; }
    static constexpr bool commute = true;
  };

  struct AM {
    using Monoid_X = Mono_Line;
    using Monoid_A = Monoid_Add<int>;
    using X = typename Monoid_X::value_type;
    using A = typename Monoid_A::value_type;
    static X act(X x, const A& a, const ll&) {
      x.left += a, x.right -= a;
      return x;
    }
  };

  using X = typename Mono_Line::value_type;
  Lazy_SegTree<AM> seg_flow;

  Dynamic_MCF_on_Line(int N, const vc<int>& right_cap, const vc<int>& left_cap)
      : N(N),
        ANS(0),
        S_remain(N),
        S_used(N),
        T_remain(N),
        T_used(N),
        seg_terminal(N) {
    assert(N > 0);
    assert(len(right_cap) == N - 1);
    assert(len(left_cap) == N - 1);
    FOR(i, N - 1) {
      assert(right_cap[i] >= 0);
      assert(left_cap[i] >= 0);
    }
    seg_flow.build(
        N - 1, [&](int i) -> X { return {left_cap[i], right_cap[i]}; });
  }

  void add_source(int v, T cost, int cap = 1) {
    assert(0 <= v && v < N);
    assert(cap >= 0);
    mp_add(S_remain[v], cost, cap);
    update_terminal(v);

    FOR(cap) {
      auto [l, r] = reachable_from(v);
      // v -> ... -> w -> hub
      auto [c, w] = seg_terminal.prod(l, r + 1).to;
      if (w == -1 || cost + c >= 0) break;
      move_mp(S_remain[v], S_used[v], cost, 1);
      ANS += cost;
      update_terminal(v);
      push_line(v, w, 1);
      push_to_hub(w, c);
    }
  }

  void add_sink(int v, T cost, int cap = 1) {
    assert(0 <= v && v < N);
    assert(cap >= 0);

    mp_add(T_remain[v], cost, cap);
    update_terminal(v);

    FOR(cap) {
      auto [l, r] = reachable_to(v);
      // hub -> w -> ... -> v
      auto [c, w] = seg_terminal.prod(l, r + 1).from;
      if (w == -1 || c + cost >= 0) break;
      push_from_hub(w, c);
      push_line(w, v, 1);
      move_mp(T_remain[v], T_used[v], cost, 1);
      ANS += cost;
      update_terminal(v);
    }
  }

  void rm_source(int v, T cost, int cap = 1) {
    assert(0 <= v && v < N);
    assert(cap >= 0);
    int a = mp_count(S_remain[v], cost);
    int b = mp_count(S_used[v], cost);
    assert(a + b >= cap);

    int k = min(cap, a);
    mp_sub(S_remain[v], cost, k);
    cap -= k;
    update_terminal(v);

    FOR(cap) {
      mp_sub(S_used[v], cost, 1);
      ANS -= cost;
      update_terminal(v);
      auto [l, r] = reachable_to(v);
      auto [c, w] = seg_terminal.prod(l, r + 1).from;
      assert(w != -1);
      push_from_hub(w, c);
      push_line(w, v, 1);
    }
  }

  void rm_sink(int v, T cost, int cap = 1) {
    assert(0 <= v && v < N);
    assert(cap >= 0);
    int a = mp_count(T_remain[v], cost);
    int b = mp_count(T_used[v], cost);
    assert(a + b >= cap);
    int k = min(cap, a);
    mp_sub(T_remain[v], cost, k);
    cap -= k;
    update_terminal(v);
    FOR(cap) {
      mp_sub(T_used[v], cost, 1);
      ANS -= cost;
      update_terminal(v);
      auto [l, r] = reachable_from(v);
      auto [c, w] = seg_terminal.prod(l, r + 1).to;
      assert(w != -1);
      push_line(v, w, 1);
      push_to_hub(w, c);
    }
  }

 private:
  static int mp_count(const map<T, int>& mp, const T& x) {
    auto it = mp.find(x);
    return (it == mp.end() ? 0 : it->second);
  }

  static void mp_add(map<T, int>& mp, const T& x, int k) {
    assert(k >= 0);
    if (k == 0) return;
    mp[x] += k;
  }

  static void mp_sub(map<T, int>& mp, const T& x, int k) {
    assert(k >= 0);
    if (k == 0) return;
    auto it = mp.find(x);
    assert(it != mp.end() && it->second >= k);
    it->second -= k;
    if (it->second == 0) mp.erase(it);
  }

  static void move_mp(map<T, int>& A, map<T, int>& B, const T& x, int k) {
    mp_sub(A, x, k), mp_add(B, x, k);
  }

  void update_terminal(int v) {
    auto x = Mono::id();
    if (!S_remain[v].empty()) chmin(x.from, P{S_remain[v].begin()->first, v});
    if (!T_used[v].empty()) chmin(x.from, P{-T_used[v].rbegin()->first, v});
    if (!T_remain[v].empty()) chmin(x.to, P{T_remain[v].begin()->first, v});
    if (!S_used[v].empty()) chmin(x.to, P{-S_used[v].rbegin()->first, v});

    seg_terminal.set(v, x);
  }

  void push_from_hub(int v, T cost) {
    if (!S_remain[v].empty() && S_remain[v].begin()->first == cost) {
      move_mp(S_remain[v], S_used[v], cost, 1);
      ANS += cost;
      update_terminal(v);
      return;
    }

    assert(!T_used[v].empty());
    T c = T_used[v].rbegin()->first;
    assert(-c == cost);

    move_mp(T_used[v], T_remain[v], c, 1);
    ANS -= c;
    update_terminal(v);
  }

  void push_to_hub(int v, T cost) {
    if (!T_remain[v].empty() && T_remain[v].begin()->first == cost) {
      move_mp(T_remain[v], T_used[v], cost, 1);
      ANS += cost;
      update_terminal(v);
      return;
    }

    assert(!S_used[v].empty());
    T c = S_used[v].rbegin()->first;
    assert(-c == cost);

    move_mp(S_used[v], S_remain[v], c, 1);
    ANS -= c;
    update_terminal(v);
  }

  // v から到達可能な vertex interval [l, r]
  pair<int, int> reachable_from(int v) {
    int l =
        seg_flow.min_left([&](const X& x) -> bool { return x.left > 0; }, v);
    int r =
        seg_flow.max_right([&](const X& x) -> bool { return x.right > 0; }, v);
    return {l, r};
  }

  // v に到達可能な vertex interval [l, r]
  pair<int, int> reachable_to(int v) {
    int l =
        seg_flow.min_left([&](const X& x) -> bool { return x.right > 0; }, v);
    int r =
        seg_flow.max_right([&](const X& x) -> bool { return x.left > 0; }, v);
    return {l, r};
  }

  void push_line(int s, int t, int f) {
    assert(f >= 0);
    if (s == t || f == 0) return;

    if (s < t) {
      assert(seg_flow.prod(s, t).right >= f);
      seg_flow.apply(s, t, +f);
    } else {
      assert(seg_flow.prod(t, s).left >= f);
      seg_flow.apply(t, s, -f);
    }
  }
};

Back to top page