ds/segtree/beats_kinetic.hpp

• View this file on GitHub
• Last update: 2026-08-30 21:09:36+09:00
• Include: #include "ds/segtree/beats_kinetic.hpp"
• Link: https://atcoder.jp/contests/jsc2024-final/tasks/jsc2024_final_d
• Link: https://codeforces.com/blog/entry/82094#comment-688448

Depends on

• ds/segtree/segtree_beats.hpp
• other/bit.hpp

Verified with

• test/1_mytest/kinetic.test.cpp

Code

#include "ds/segtree/segtree_beats.hpp"

// (x[i],y[i]) からなる列. a>=0 であるときに y[i] := y[i] + ax[i] + b
// という作用ができる x には単調性は要らない. x,sum(a):T1, y,sum(b):T2,
// T1*T1<=T2. https://codeforces.com/blog/entry/82094#comment-688448
// https://atcoder.jp/contests/jsc2024-final/tasks/jsc2024_final_d
template <typename T1, typename T2>
struct Beats_Kinetic_Max {
  struct Mono_X {
    struct X {
      int idx;
      T1 x;
      T2 y;
      T1 nxt_change;
      bool fail;
    };
    using value_type = X;
    static X op(X L, X R) {
      X M;
      if (L.y < R.y) {
        swap(L, R);
      }
      M.idx = L.idx, M.x = L.x, M.y = L.y;
      M.nxt_change = min(L.nxt_change, R.nxt_change);
      if (L.x < R.x) {
        T2 t = floor<T2>(L.y - R.y, R.x - L.x);
        M.nxt_change = min<T2>(M.nxt_change, t + 1);
      }
      M.fail = 0;
      return M;
    }
    static constexpr X id() { return {-1, 0, -infty<T2>, infty<T1>, 0}; }
    bool commute = true;
  };
  struct Mono_A {
    using X = pair<T1, T2>;
    using value_type = X;
    static constexpr X op(const X& x, const X& y) {
      return {x.fi + y.fi, x.se + y.se};
    }
    static constexpr X id() { return {0, 0}; }
    bool commute = true;
  };
  struct Beats {
    using Monoid_X = Mono_X;
    using Monoid_A = Mono_A;
    using X = typename Monoid_X::value_type;
    using A = typename Monoid_A::value_type;
    static X act(X& M, const A& a, int cnt) {
      assert(!M.fail && a.fi >= 0);
      if (M.nxt_change <= a.fi) {
        M.fail = 1;
        return M;
      }
      M.y += T2(a.fi) * M.x + a.se;
      M.nxt_change -= a.fi;
      return M;
    }
  };
  using S = typename Mono_X::X;
  SegTree_Beats<Beats> seg;
  Beats_Kinetic_Max(vc<T1>& X, vc<T2>& Y) {
    seg.build(len(X),
              [&](int i) -> S { return {i, X[i], Y[i], infty<T1>, 0}; });
  }
  template <typename F>
  Beats_Kinetic_Max(int n, F f) {
    seg.build(n, [&](int i) -> S {
      auto [x, y] = f(i);
      return {i, x, y, infty<T1>, 0};
    });
  }

  void set(int i, T1 x, T2 y) { seg.set(i, {i, x, y, infty<T1>, 0}); }

  // (i,x,y)
  tuple<int, T1, T2> prod(int l, int r) {
    auto e = seg.prod(l, r);
    return {e.idx, e.x, e.y};
  }
  // (i,x,y)
  tuple<int, T1, T2> prod_all() {
    auto e = seg.prod_all();
    return {e.idx, e.x, e.y};
  }
  // y[i] := y[i] + ax[i] + b
  void apply(int l, int r, T1 a, T2 b) { seg.apply(l, r, {a, b}); }
};

// (x[i],y[i]) からなる列. a>=0 であるときに y[i] := y[i] + ax[i] + b
// という作用ができる x には単調性は要らない. x,sum(a):T1, y,sum(b):T2,
// T1*T1<=T2. https://codeforces.com/blog/entry/82094#comment-688448
// https://atcoder.jp/contests/jsc2024-final/tasks/jsc2024_final_d
template <typename T1, typename T2>
struct Beats_Kinetic_Min {
  struct Mono_X {
    struct X {
      int idx;
      T1 x;
      T2 y;
      T1 nxt_change;
      bool fail;
    };
    using value_type = X;
    static X op(X L, X R) {
      X M;
      if (L.y > R.y) {
        swap(L, R);
      }
      M.idx = L.idx, M.x = L.x, M.y = L.y;
      M.nxt_change = min(L.nxt_change, R.nxt_change);
      if (L.x > R.x) {
        T2 t = floor<T2>(R.y - L.y, L.x - R.x);
        M.nxt_change = min<T2>(M.nxt_change, t + 1);
      }
      M.fail = 0;
      return M;
    }
    static constexpr X id() { return {-1, 0, infty<T2>, infty<T1>, 0}; }
    bool commute = true;
  };
  struct Mono_A {
    using X = pair<T1, T2>;
    using value_type = X;
    static constexpr X op(const X& x, const X& y) {
      return {x.fi + y.fi, x.se + y.se};
    }
    static constexpr X id() { return {0, 0}; }
    bool commute = true;
  };
  struct Beats {
    using Monoid_X = Mono_X;
    using Monoid_A = Mono_A;
    using X = typename Monoid_X::value_type;
    using A = typename Monoid_A::value_type;
    static X act(X& M, const A& a, int cnt) {
      assert(!M.fail && a.fi >= 0);
      if (M.nxt_change <= a.fi) {
        M.fail = 1;
        return M;
      }
      M.y += T2(a.fi) * M.x + a.se;
      M.nxt_change -= a.fi;
      return M;
    }
  };
  using S = typename Mono_X::X;
  SegTree_Beats<Beats> seg;
  Beats_Kinetic_Min(vc<T1>& X, vc<T2>& Y) {
    seg.build(len(X),
              [&](int i) -> S { return {i, X[i], Y[i], infty<T1>, 0}; });
  }
  template <typename F>
  Beats_Kinetic_Min(int n, F f) {
    seg.build(n, [&](int i) -> S {
      auto [x, y] = f(i);
      return {i, x, y, infty<T1>, 0};
    });
  }

  void set(int i, T1 x, T2 y) { seg.set(i, {i, x, y, infty<T1>, 0}); }

  // (i,x,y)
  tuple<int, T1, T2> prod(int l, int r) {
    auto e = seg.prod(l, r);
    return {e.idx, e.x, e.y};
  }
  tuple<int, T1, T2> prod_all() {
    auto e = seg.prod_all();
    return {e.idx, e.x, e.y};
  }

  // y[i] := y[i] + ax[i] + b
  void apply(int l, int r, T1 a, T2 b) { seg.apply(l, r, {a, b}); }
};

#line 1 "other/bit.hpp"

int popcnt(int x) { return __builtin_popcount(x); }
int popcnt(u32 x) { return __builtin_popcount(x); }
int popcnt(ll x) { return __builtin_popcountll(x); }
int popcnt(u64 x) { return __builtin_popcountll(x); }
int popcnt_sgn(int x) { return (__builtin_parity(unsigned(x)) & 1 ? -1 : 1); }
int popcnt_sgn(u32 x) { return (__builtin_parity(x) & 1 ? -1 : 1); }
int popcnt_sgn(ll x) { return (__builtin_parityll(x) & 1 ? -1 : 1); }
int popcnt_sgn(u64 x) { return (__builtin_parityll(x) & 1 ? -1 : 1); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 1, 2)
int topbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(u32 x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(ll x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
int topbit(u64 x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 0, 2)
int lowbit(int x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(u32 x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(ll x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
int lowbit(u64 x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }

template <typename T>
T kth_bit(int k) {
  assert(0 <= k && k < int(8 * sizeof(T)));
  return T(1) << k;
}
template <typename T>
bool has_kth_bit(T x, int k) {
  assert(0 <= k && k < int(8 * sizeof(T)));
  return x >> k & 1;
}

template <typename UINT>
struct all_bit {
  static_assert(is_unsigned<UINT>::value);
  UINT s;
  all_bit(UINT s) : s(s) {}
  struct iter {
    UINT s;
    int operator*() const { return lowbit(s); }
    void operator++() { s &= s - 1; }
    bool operator!=(nullptr_t) const { return s; }
  };
  iter begin() const { return {s}; }
  nullptr_t end() const { return nullptr; }
};

template <typename UINT>
struct all_subset {
  static_assert(is_unsigned<UINT>::value);
  UINT s;
  all_subset(UINT s) : s(s) {}
  struct iter {
    UINT s, t;
    bool done = false;
    UINT operator*() const { return t; }
    void operator++() {
      done = (t == 0);
      t = (t - 1) & s;
    }
    bool operator!=(nullptr_t) const { return !done; }
  };
  iter begin() const { return {s, s}; }
  nullptr_t end() const { return nullptr; }
};

constexpr u64 full_mask(int n) {
  assert(0 <= n && n <= 64);
  return n == 64 ? -1ULL : (1ULL << n) - 1;
}

u64 bit_reverse(u64 x) {
  x = ((x & 0x5555555555555555ULL) << 1) | ((x >> 1) & 0x5555555555555555ULL);
  x = ((x & 0x3333333333333333ULL) << 2) | ((x >> 2) & 0x3333333333333333ULL);
  x = ((x & 0x0f0f0f0f0f0f0f0fULL) << 4) | ((x >> 4) & 0x0f0f0f0f0f0f0f0fULL);
  x = ((x & 0x00ff00ff00ff00ffULL) << 8) | ((x >> 8) & 0x00ff00ff00ff00ffULL);
  x = ((x & 0x0000ffff0000ffffULL) << 16) | ((x >> 16) & 0x0000ffff0000ffffULL);
  x = (x << 32) | (x >> 32);
  return x;
}
#line 2 "ds/segtree/segtree_beats.hpp"

template <typename ActedMonoid>
struct SegTree_Beats {
  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;

  SegTree_Beats() {}
  SegTree_Beats(int n) { build(n); }
  template <typename F>
  SegTree_Beats(int n, F f) {
    build(n, f);
  }
  SegTree_Beats(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 = 1;
    while ((1 << log) < n) ++log;
    size = 1 << log;
    dat.assign(size << 1, MX::id());
    laz.assign(size, MA::id());
    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);
  }

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

  /*
  void all_apply(int k, A a) {
    dat[k] = ActedMonoid::act(dat[k], a);
    if (k < size) {
      laz[k] = MA::op(laz[k], a);
      if (dat[k].fail) push(k), update(k);
    }
  }
  */

  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);
    }
  }

 private:
  void apply_at(int k, A a) {
    int sz = 1 << (log - topbit(k));
    dat[k] = AM::act(dat[k], a, sz);
    if (k < size) {
      laz[k] = MA::op(laz[k], a);
      if (dat[k].fail) push(k), update(k);
    }
  }

  void push(int k) {
    if (laz[k] == MA::id()) return;
    apply_at(2 * k, laz[k]), apply_at(2 * k + 1, laz[k]);
    laz[k] = MA::id();
  }
};
#line 2 "ds/segtree/beats_kinetic.hpp"

// (x[i],y[i]) からなる列. a>=0 であるときに y[i] := y[i] + ax[i] + b
// という作用ができる x には単調性は要らない. x,sum(a):T1, y,sum(b):T2,
// T1*T1<=T2. https://codeforces.com/blog/entry/82094#comment-688448
// https://atcoder.jp/contests/jsc2024-final/tasks/jsc2024_final_d
template <typename T1, typename T2>
struct Beats_Kinetic_Max {
  struct Mono_X {
    struct X {
      int idx;
      T1 x;
      T2 y;
      T1 nxt_change;
      bool fail;
    };
    using value_type = X;
    static X op(X L, X R) {
      X M;
      if (L.y < R.y) {
        swap(L, R);
      }
      M.idx = L.idx, M.x = L.x, M.y = L.y;
      M.nxt_change = min(L.nxt_change, R.nxt_change);
      if (L.x < R.x) {
        T2 t = floor<T2>(L.y - R.y, R.x - L.x);
        M.nxt_change = min<T2>(M.nxt_change, t + 1);
      }
      M.fail = 0;
      return M;
    }
    static constexpr X id() { return {-1, 0, -infty<T2>, infty<T1>, 0}; }
    bool commute = true;
  };
  struct Mono_A {
    using X = pair<T1, T2>;
    using value_type = X;
    static constexpr X op(const X& x, const X& y) {
      return {x.fi + y.fi, x.se + y.se};
    }
    static constexpr X id() { return {0, 0}; }
    bool commute = true;
  };
  struct Beats {
    using Monoid_X = Mono_X;
    using Monoid_A = Mono_A;
    using X = typename Monoid_X::value_type;
    using A = typename Monoid_A::value_type;
    static X act(X& M, const A& a, int cnt) {
      assert(!M.fail && a.fi >= 0);
      if (M.nxt_change <= a.fi) {
        M.fail = 1;
        return M;
      }
      M.y += T2(a.fi) * M.x + a.se;
      M.nxt_change -= a.fi;
      return M;
    }
  };
  using S = typename Mono_X::X;
  SegTree_Beats<Beats> seg;
  Beats_Kinetic_Max(vc<T1>& X, vc<T2>& Y) {
    seg.build(len(X),
              [&](int i) -> S { return {i, X[i], Y[i], infty<T1>, 0}; });
  }
  template <typename F>
  Beats_Kinetic_Max(int n, F f) {
    seg.build(n, [&](int i) -> S {
      auto [x, y] = f(i);
      return {i, x, y, infty<T1>, 0};
    });
  }

  void set(int i, T1 x, T2 y) { seg.set(i, {i, x, y, infty<T1>, 0}); }

  // (i,x,y)
  tuple<int, T1, T2> prod(int l, int r) {
    auto e = seg.prod(l, r);
    return {e.idx, e.x, e.y};
  }
  // (i,x,y)
  tuple<int, T1, T2> prod_all() {
    auto e = seg.prod_all();
    return {e.idx, e.x, e.y};
  }
  // y[i] := y[i] + ax[i] + b
  void apply(int l, int r, T1 a, T2 b) { seg.apply(l, r, {a, b}); }
};

// (x[i],y[i]) からなる列. a>=0 であるときに y[i] := y[i] + ax[i] + b
// という作用ができる x には単調性は要らない. x,sum(a):T1, y,sum(b):T2,
// T1*T1<=T2. https://codeforces.com/blog/entry/82094#comment-688448
// https://atcoder.jp/contests/jsc2024-final/tasks/jsc2024_final_d
template <typename T1, typename T2>
struct Beats_Kinetic_Min {
  struct Mono_X {
    struct X {
      int idx;
      T1 x;
      T2 y;
      T1 nxt_change;
      bool fail;
    };
    using value_type = X;
    static X op(X L, X R) {
      X M;
      if (L.y > R.y) {
        swap(L, R);
      }
      M.idx = L.idx, M.x = L.x, M.y = L.y;
      M.nxt_change = min(L.nxt_change, R.nxt_change);
      if (L.x > R.x) {
        T2 t = floor<T2>(R.y - L.y, L.x - R.x);
        M.nxt_change = min<T2>(M.nxt_change, t + 1);
      }
      M.fail = 0;
      return M;
    }
    static constexpr X id() { return {-1, 0, infty<T2>, infty<T1>, 0}; }
    bool commute = true;
  };
  struct Mono_A {
    using X = pair<T1, T2>;
    using value_type = X;
    static constexpr X op(const X& x, const X& y) {
      return {x.fi + y.fi, x.se + y.se};
    }
    static constexpr X id() { return {0, 0}; }
    bool commute = true;
  };
  struct Beats {
    using Monoid_X = Mono_X;
    using Monoid_A = Mono_A;
    using X = typename Monoid_X::value_type;
    using A = typename Monoid_A::value_type;
    static X act(X& M, const A& a, int cnt) {
      assert(!M.fail && a.fi >= 0);
      if (M.nxt_change <= a.fi) {
        M.fail = 1;
        return M;
      }
      M.y += T2(a.fi) * M.x + a.se;
      M.nxt_change -= a.fi;
      return M;
    }
  };
  using S = typename Mono_X::X;
  SegTree_Beats<Beats> seg;
  Beats_Kinetic_Min(vc<T1>& X, vc<T2>& Y) {
    seg.build(len(X),
              [&](int i) -> S { return {i, X[i], Y[i], infty<T1>, 0}; });
  }
  template <typename F>
  Beats_Kinetic_Min(int n, F f) {
    seg.build(n, [&](int i) -> S {
      auto [x, y] = f(i);
      return {i, x, y, infty<T1>, 0};
    });
  }

  void set(int i, T1 x, T2 y) { seg.set(i, {i, x, y, infty<T1>, 0}); }

  // (i,x,y)
  tuple<int, T1, T2> prod(int l, int r) {
    auto e = seg.prod(l, r);
    return {e.idx, e.x, e.y};
  }
  tuple<int, T1, T2> prod_all() {
    auto e = seg.prod_all();
    return {e.idx, e.x, e.y};
  }

  // y[i] := y[i] + ax[i] + b
  void apply(int l, int r, T1 a, T2 b) { seg.apply(l, r, {a, b}); }
};

Back to top page