This documentation is automatically generated by online-judge-tools/verification-helper
#include "ds/segtree/beats_kinetic.hpp"
#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);
chmin(M.nxt_change, t + 1);
}
M.fail = 0;
return M;
}
static constexpr X unit() { 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 unit() { 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);
chmin(M.nxt_change, t + 1);
}
M.fail = 0;
return M;
}
static constexpr X unit() { 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 unit() { 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 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::unit(); });
}
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::unit());
laz.assign(size, MA::unit());
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::unit();
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::unit(), xr = MX::unit();
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::unit()) return;
apply_at(2 * k, laz[k]), apply_at(2 * k + 1, laz[k]);
laz[k] = MA::unit();
}
};
#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);
chmin(M.nxt_change, t + 1);
}
M.fail = 0;
return M;
}
static constexpr X unit() { 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 unit() { 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);
chmin(M.nxt_change, t + 1);
}
M.fail = 0;
return M;
}
static constexpr X unit() { 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 unit() { 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}); }
};