This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub AlexanderNekrasov/Youthful-Passion-Fruit-teambook
/** * Author: Alexey Vasilyev * Date: 2024-08-20 * Description: kinetic segment tree * Time: O(hz) */ //vnutrennii functions - poluintervali, vneshnie - otrezki. ishet min priamuy struct line { ll k,b,temp; ll eval() const { return k * temp + b; } ll melting_point(const line& other) const { ll val1 = eval(); ll val2 = other.eval(); assert(val1 <= val2); if (other.k >= k) { return INF; } ll delta_val = val2 - val1; ll delta_k = k - other.k; assert(delta_val >= 0 && delta_k > 0); return (delta_val + delta_k - 1) / delta_k; } }; struct kinetic_segtree { struct node { ll lazy_b = 0, lazy_temp = 0, melt = INF; line best; node(line best = line()) : best(best) {} }; int n; vector<node> tree; void update(int v) { if (make_pair(tree[v << 1].best.eval(), tree[v << 1].best.k) < make_pair(tree[v << 1 | 1].best.eval(), tree[v << 1 | 1].best.k)) { tree[v].best = tree[v << 1].best; tree[v].melt = tree[v].best.melting_point(tree[v << 1 | 1].best); } else { tree[v].best = tree[v << 1 | 1].best; tree[v].melt = tree[v].best.melting_point(tree[v << 1].best); } tree[v].melt = min({tree[v].melt, tree[v << 1].melt, tree[v << 1 | 1].melt}); assert(tree[v].melt > 0); } void apply(int v, int vl, int vr, ll delta_b, ll delta_temp) { tree[v].lazy_b += delta_b; tree[v].lazy_temp += delta_temp; tree[v].best.b += delta_b; tree[v].best.temp += delta_temp; tree[v].melt -= delta_temp; if (tree[v].melt <= 0) { push(v, vl, vr); update(v); } } void push(int v, int vl, int vr) { int vm = (vl + vr) / 2; apply(v << 1, vl, vm, tree[v].lazy_b, tree[v].lazy_temp); apply(v << 1 | 1, vm, vr, tree[v].lazy_b, tree[v].lazy_temp); tree[v].lazy_b = 0; tree[v].lazy_temp = 0; } void build(int v, int vl, int vr, const vector<line> &lines) { if (vr - vl == 1) { tree[v] = node(lines[vl]); return; } int vm = (vl + vr) / 2; build(v << 1, vl, vm, lines); build(v << 1 | 1, vm, vr, lines); update(v); } void add(int v, int vl, int vr, int l, int r, ll delta_b, ll delta_temp) { if (r <= vl || vr <= l) { return; } if (l <= vl && vr <= r) { apply(v, vl, vr, delta_b, delta_temp); return; } push(v, vl, vr); int vm = (vl + vr) / 2; add(v << 1, vl, vm, l, r, delta_b, delta_temp); add(v << 1 | 1, vm, vr, l, r, delta_b, delta_temp); update(v); } void change_line(int v, int vl, int vr, int pos, const line &new_line) { if (vr - vl == 1) { tree[v].best = new_line; return; } push(v, vl, vr); int vm = (vl + vr) / 2; if (pos < vm) { change_line(v << 1, vl, vm, pos, new_line); } else { change_line(v << 1 | 1, vm, vr, pos, new_line); } update(v); } ll query(int v, int vl, int vr, int l, int r) { if (r <= vl || vr <= l) { return INF; } if (l <= vl && vr <= r) { return tree[v].best.eval(); } push(v, vl, vr); int vm = (vl + vr) / 2; return min(query(v << 1, vl, vm, l, r), query(v << 1 | 1, vm, vr, l, r)); } kinetic_segtree(const vector<line> &lines) : n(lines.size()), tree(4 * n) { build(1, 0, n, lines); } kinetic_segtree(int n) : n(n), tree(4 * n) { vector <line> lines(n, {0, INF, 0}); build(1, 0, n, lines); } void add(int l, int r, ll delta_b, ll delta_temp) { assert(delta_temp >= 0); add(1, 0, n, l, r + 1, delta_b, delta_temp); } void change_line(int pos, const line &new_line) { assert(0 <= pos && pos < n); change_line(1, 0, n, pos, new_line); } ll query(int l, int r) { return query(1, 0, n, l, r + 1); } }
#line 1 "geometry/Kinetic.cpp" /** * Author: Alexey Vasilyev * Date: 2024-08-20 * Description: kinetic segment tree * Time: O(hz) */ //vnutrennii functions - poluintervali, vneshnie - otrezki. ishet min priamuy struct line { ll k,b,temp; ll eval() const { return k * temp + b; } ll melting_point(const line& other) const { ll val1 = eval(); ll val2 = other.eval(); assert(val1 <= val2); if (other.k >= k) { return INF; } ll delta_val = val2 - val1; ll delta_k = k - other.k; assert(delta_val >= 0 && delta_k > 0); return (delta_val + delta_k - 1) / delta_k; } }; struct kinetic_segtree { struct node { ll lazy_b = 0, lazy_temp = 0, melt = INF; line best; node(line best = line()) : best(best) {} }; int n; vector<node> tree; void update(int v) { if (make_pair(tree[v << 1].best.eval(), tree[v << 1].best.k) < make_pair(tree[v << 1 | 1].best.eval(), tree[v << 1 | 1].best.k)) { tree[v].best = tree[v << 1].best; tree[v].melt = tree[v].best.melting_point(tree[v << 1 | 1].best); } else { tree[v].best = tree[v << 1 | 1].best; tree[v].melt = tree[v].best.melting_point(tree[v << 1].best); } tree[v].melt = min({tree[v].melt, tree[v << 1].melt, tree[v << 1 | 1].melt}); assert(tree[v].melt > 0); } void apply(int v, int vl, int vr, ll delta_b, ll delta_temp) { tree[v].lazy_b += delta_b; tree[v].lazy_temp += delta_temp; tree[v].best.b += delta_b; tree[v].best.temp += delta_temp; tree[v].melt -= delta_temp; if (tree[v].melt <= 0) { push(v, vl, vr); update(v); } } void push(int v, int vl, int vr) { int vm = (vl + vr) / 2; apply(v << 1, vl, vm, tree[v].lazy_b, tree[v].lazy_temp); apply(v << 1 | 1, vm, vr, tree[v].lazy_b, tree[v].lazy_temp); tree[v].lazy_b = 0; tree[v].lazy_temp = 0; } void build(int v, int vl, int vr, const vector<line> &lines) { if (vr - vl == 1) { tree[v] = node(lines[vl]); return; } int vm = (vl + vr) / 2; build(v << 1, vl, vm, lines); build(v << 1 | 1, vm, vr, lines); update(v); } void add(int v, int vl, int vr, int l, int r, ll delta_b, ll delta_temp) { if (r <= vl || vr <= l) { return; } if (l <= vl && vr <= r) { apply(v, vl, vr, delta_b, delta_temp); return; } push(v, vl, vr); int vm = (vl + vr) / 2; add(v << 1, vl, vm, l, r, delta_b, delta_temp); add(v << 1 | 1, vm, vr, l, r, delta_b, delta_temp); update(v); } void change_line(int v, int vl, int vr, int pos, const line &new_line) { if (vr - vl == 1) { tree[v].best = new_line; return; } push(v, vl, vr); int vm = (vl + vr) / 2; if (pos < vm) { change_line(v << 1, vl, vm, pos, new_line); } else { change_line(v << 1 | 1, vm, vr, pos, new_line); } update(v); } ll query(int v, int vl, int vr, int l, int r) { if (r <= vl || vr <= l) { return INF; } if (l <= vl && vr <= r) { return tree[v].best.eval(); } push(v, vl, vr); int vm = (vl + vr) / 2; return min(query(v << 1, vl, vm, l, r), query(v << 1 | 1, vm, vr, l, r)); } kinetic_segtree(const vector<line> &lines) : n(lines.size()), tree(4 * n) { build(1, 0, n, lines); } kinetic_segtree(int n) : n(n), tree(4 * n) { vector <line> lines(n, {0, INF, 0}); build(1, 0, n, lines); } void add(int l, int r, ll delta_b, ll delta_temp) { assert(delta_temp >= 0); add(1, 0, n, l, r + 1, delta_b, delta_temp); } void change_line(int pos, const line &new_line) { assert(0 <= pos && pos < n); change_line(1, 0, n, pos, new_line); } ll query(int l, int r) { return query(1, 0, n, l, r + 1); } }