range_linear_add_range_min.hpp¶
给区间加入关于下标的一次函数，并查询区间最小值；适合斜率更新与区间最值同时出现的题目。
Complexity: Time: O(n log n) construction and O(log^2 n) per update/query. Space: O(n).
AC 记录：range_linear_add_range_min。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(n log n) construction and O(log^2 n) per update/query.
/// Space: O(n).
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <limits>
#include <vector>
namespace noya {
/// @brief Maintain an integer sequence under adding b*i+c on a range and
/// range-minimum queries. Regard every value as a point (i, a_i). A segment
/// tree node represents the lower convex hull of its points by the common
/// tangent (bridge) between the two child hulls. Adding the same linear
/// function to a whole node shears all of its points and preserves that hull,
/// so it is stored lazily. When the children receive different additions, the
/// bridge is restored by descending their existing bridges to the new common
/// tangent. A minimum is found by following decreasing bridge endpoints.
class range_linear_add_range_min {
public:
using value_type = long long;
range_linear_add_range_min() { build({}); }
explicit range_linear_add_range_min(const std::vector<value_type> &arr) {
build(arr);
}
void build(const std::vector<value_type> &arr) {
n0 = int(arr.size());
n = 1;
h = 0;
while (n < std::max(1, n0)) {
n <<= 1;
h++;
}
a0.resize(2 * n);
lz.assign(2 * n, {});
br.resize(2 * n);
constexpr value_type inf = std::numeric_limits<value_type>::max() / 4;
for (int idx = 0; idx < n; idx++) {
value_type val = idx < n0 ? arr[idx] : inf;
a0[n + idx] = {idx, val};
br[n + idx] = {a0[n + idx], a0[n + idx]};
}
for (int u = n - 1; u > 0; u--) {
rebuild_bridge(u);
}
}
int size() const { return n0; }
/// @brief Add slope*i+intercept to every a_i with i in [l, r).
void range_add(int l, int r, value_type k, value_type B) {
assert(0 <= l && l <= r && r <= n0);
if (l == r) {
return;
}
int lc = l + n;
int rc = r + n;
while (lc < rc) {
if (lc & 1) {
lz[lc] += line{k, B};
lc++;
}
lc >>= 1;
if (rc & 1) {
--rc;
lz[rc] += line{k, B};
}
rc >>= 1;
}
lc = l + n;
rc = r + n;
for (int dep = 1; dep <= h; dep++) {
if ((lc >> dep << dep) != lc) {
rebuild_bridge(lc >> dep);
}
if ((rc >> dep << dep) != rc) {
rebuild_bridge((rc - 1) >> dep);
}
}
}
/// @brief Return min(a_i) over the nonempty range [l, r).
value_type range_min(int l, int r) const {
assert(0 <= l && l < r && r <= n0);
int lc = l + n;
int rc = r + n;
value_type ans = std::numeric_limits<value_type>::max();
while (lc < rc) {
if (lc & 1) {
ans = std::min(ans, subtree_minimum(lc++));
}
lc >>= 1;
if (rc & 1) {
ans = std::min(ans, subtree_minimum(--rc));
}
rc >>= 1;
}
return ans;
}
private:
using wide_type = __int128_t;
struct point {
value_type x = 0;
value_type y = 0;
friend point operator-(point A, point rhs) {
return {A.x - rhs.x, A.y - rhs.y};
}
friend bool operator==(point A, point rhs) {
return A.x == rhs.x && A.y == rhs.y;
}
};
struct line {
value_type k = 0;
value_type B = 0;
line &operator+=(line rh0) {
k += rh0.k;
B += rh0.B;
return *this;
}
};
struct bridge {
point l;
point r;
};
int n0 = 0;
int n = 1;
int h = 0;
std::vector<point> a0;
std::vector<line> lz;
std::vector<bridge> br;
static wide_type cross(point A, point rhs) {
return wide_type(A.x) * rhs.y - wide_type(A.y) * rhs.x;
}
static point apply(point val, line add) {
val.y += val.x * add.k + add.B;
return val;
}
void rebuild_bridge(int u) {
if (u >= n) {
return;
}
line aa;
for (int fa = u; fa > 0; fa >>= 1) {
aa += lz[fa];
}
int lc = u * 2;
int rc = u * 2 + 1;
int lim = rc;
while (lim < n) {
lim <<= 1;
}
lim -= n;
line al = lz[lc];
line ar = lz[rc];
while (lc < n || rc < n) {
point a = apply(apply(br[lc].l, aa), al);
point b = apply(apply(br[lc].r, aa), al);
point c = apply(apply(br[rc].l, aa), ar);
point d = apply(apply(br[rc].r, aa), ar);
if (!(a == b) && cross(b - a, c - a) < 0) {
lc *= 2;
al += lz[lc];
} else if (!(c == d) && cross(c - b, d - b) < 0) {
rc = rc * 2 + 1;
ar += lz[rc];
} else if (a == b) {
rc *= 2;
ar += lz[rc];
} else if (c == d) {
lc = lc * 2 + 1;
al += lz[lc];
} else {
wide_type c1 = cross(b - a, d - c);
wide_type c2 = cross(b - a, b - c);
bool dir;
if (c1 == 0 && c2 == 0) {
dir = c.x < lim;
} else {
dir = wide_type(c.x) * c1 + wide_type(d.x - c.x) * c2 < c1 * lim;
}
if (dir) {
lc = lc * 2 + 1;
al += lz[lc];
} else {
rc *= 2;
ar += lz[rc];
}
}
}
br[u] = {apply(a0[lc], al), apply(a0[rc], ar)};
}
value_type subtree_minimum(int u) const {
line add;
for (int fa = u; fa > 0; fa >>= 1) {
add += lz[fa];
}
while (u < n) {
point l = apply(br[u].l, add);
point r = apply(br[u].r, add);
u = l.y < r.y ? u * 2 : u * 2 + 1;
add += lz[u];
}
return apply(a0[u], add).y;
}
};
} // namespace noya
#ifndef NOYA_RANGE_LINEAR_ADD_RANGE_MIN_HPP
#define NOYA_RANGE_LINEAR_ADD_RANGE_MIN_HPP 1
/// @complexity Time: O(n log n) construction and O(log^2 n) per update/query.
/// Space: O(n).
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <limits>
#include <vector>
namespace noya {
/// @brief Maintain an integer sequence under adding b*i+c on a range and
/// range-minimum queries. Regard every value as a point (i, a_i). A segment
/// tree node represents the lower convex hull of its points by the common
/// tangent (bridge) between the two child hulls. Adding the same linear
/// function to a whole node shears all of its points and preserves that hull,
/// so it is stored lazily. When the children receive different additions, the
/// bridge is restored by descending their existing bridges to the new common
/// tangent. A minimum is found by following decreasing bridge endpoints.
class range_linear_add_range_min {
public:
using value_type = long long;
range_linear_add_range_min() { build({}); }
explicit range_linear_add_range_min(const std::vector<value_type> &arr) {
build(arr);
}
void build(const std::vector<value_type> &arr) {
n0 = int(arr.size());
n = 1;
h = 0;
while (n < std::max(1, n0)) {
n <<= 1;
h++;
}
a0.resize(2 * n);
lz.assign(2 * n, {});
br.resize(2 * n);
constexpr value_type inf = std::numeric_limits<value_type>::max() / 4;
for (int idx = 0; idx < n; idx++) {
value_type val = idx < n0 ? arr[idx] : inf;
a0[n + idx] = {idx, val};
br[n + idx] = {a0[n + idx], a0[n + idx]};
}
for (int u = n - 1; u > 0; u--) {
rebuild_bridge(u);
}
}
int size() const { return n0; }
/// @brief Add slope*i+intercept to every a_i with i in [l, r).
void range_add(int l, int r, value_type k, value_type B) {
assert(0 <= l && l <= r && r <= n0);
if (l == r) {
return;
}
int lc = l + n;
int rc = r + n;
while (lc < rc) {
if (lc & 1) {
lz[lc] += line{k, B};
lc++;
}
lc >>= 1;
if (rc & 1) {
--rc;
lz[rc] += line{k, B};
}
rc >>= 1;
}
lc = l + n;
rc = r + n;
for (int dep = 1; dep <= h; dep++) {
if ((lc >> dep << dep) != lc) {
rebuild_bridge(lc >> dep);
}
if ((rc >> dep << dep) != rc) {
rebuild_bridge((rc - 1) >> dep);
}
}
}
/// @brief Return min(a_i) over the nonempty range [l, r).
value_type range_min(int l, int r) const {
assert(0 <= l && l < r && r <= n0);
int lc = l + n;
int rc = r + n;
value_type ans = std::numeric_limits<value_type>::max();
while (lc < rc) {
if (lc & 1) {
ans = std::min(ans, subtree_minimum(lc++));
}
lc >>= 1;
if (rc & 1) {
ans = std::min(ans, subtree_minimum(--rc));
}
rc >>= 1;
}
return ans;
}
private:
using wide_type = __int128_t;
struct point {
value_type x = 0;
value_type y = 0;
friend point operator-(point A, point rhs) {
return {A.x - rhs.x, A.y - rhs.y};
}
friend bool operator==(point A, point rhs) {
return A.x == rhs.x && A.y == rhs.y;
}
};
struct line {
value_type k = 0;
value_type B = 0;
line &operator+=(line rh0) {
k += rh0.k;
B += rh0.B;
return *this;
}
};
struct bridge {
point l;
point r;
};
int n0 = 0;
int n = 1;
int h = 0;
std::vector<point> a0;
std::vector<line> lz;
std::vector<bridge> br;
static wide_type cross(point A, point rhs) {
return wide_type(A.x) * rhs.y - wide_type(A.y) * rhs.x;
}
static point apply(point val, line add) {
val.y += val.x * add.k + add.B;
return val;
}
void rebuild_bridge(int u) {
if (u >= n) {
return;
}
line aa;
for (int fa = u; fa > 0; fa >>= 1) {
aa += lz[fa];
}
int lc = u * 2;
int rc = u * 2 + 1;
int lim = rc;
while (lim < n) {
lim <<= 1;
}
lim -= n;
line al = lz[lc];
line ar = lz[rc];
while (lc < n || rc < n) {
point a = apply(apply(br[lc].l, aa), al);
point b = apply(apply(br[lc].r, aa), al);
point c = apply(apply(br[rc].l, aa), ar);
point d = apply(apply(br[rc].r, aa), ar);
if (!(a == b) && cross(b - a, c - a) < 0) {
lc *= 2;
al += lz[lc];
} else if (!(c == d) && cross(c - b, d - b) < 0) {
rc = rc * 2 + 1;
ar += lz[rc];
} else if (a == b) {
rc *= 2;
ar += lz[rc];
} else if (c == d) {
lc = lc * 2 + 1;
al += lz[lc];
} else {
wide_type c1 = cross(b - a, d - c);
wide_type c2 = cross(b - a, b - c);
bool dir;
if (c1 == 0 && c2 == 0) {
dir = c.x < lim;
} else {
dir = wide_type(c.x) * c1 + wide_type(d.x - c.x) * c2 < c1 * lim;
}
if (dir) {
lc = lc * 2 + 1;
al += lz[lc];
} else {
rc *= 2;
ar += lz[rc];
}
}
}
br[u] = {apply(a0[lc], al), apply(a0[rc], ar)};
}
value_type subtree_minimum(int u) const {
line add;
for (int fa = u; fa > 0; fa >>= 1) {
add += lz[fa];
}
while (u < n) {
point l = apply(br[u].l, add);
point r = apply(br[u].r, add);
u = l.y < r.y ? u * 2 : u * 2 + 1;
add += lz[u];
}
return apply(a0[u], add).y;
}
};
} // namespace noya
#endif // NOYA_RANGE_LINEAR_ADD_RANGE_MIN_HPP
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <limits>
#include <vector>
/// @complexity Time: O(n log n) construction and O(log^2 n) per update/query.
/// Space: O(n).
namespace noya {
/// @brief Maintain an integer sequence under adding b*i+c on a range and
/// range-minimum queries. Regard every value as a point (i, a_i). A segment
/// tree node represents the lower convex hull of its points by the common
/// tangent (bridge) between the two child hulls. Adding the same linear
/// function to a whole node shears all of its points and preserves that hull,
/// so it is stored lazily. When the children receive different additions, the
/// bridge is restored by descending their existing bridges to the new common
/// tangent. A minimum is found by following decreasing bridge endpoints.
class range_linear_add_range_min {
public:
using value_type = long long;
range_linear_add_range_min() { build({}); }
explicit range_linear_add_range_min(const std::vector<value_type> &arr) {
build(arr);
}
void build(const std::vector<value_type> &arr) {
n0 = int(arr.size());
n = 1;
h = 0;
while (n < std::max(1, n0)) {
n <<= 1;
h++;
}
a0.resize(2 * n);
lz.assign(2 * n, {});
br.resize(2 * n);
constexpr value_type inf = std::numeric_limits<value_type>::max() / 4;
for (int idx = 0; idx < n; idx++) {
value_type val = idx < n0 ? arr[idx] : inf;
a0[n + idx] = {idx, val};
br[n + idx] = {a0[n + idx], a0[n + idx]};
}
for (int u = n - 1; u > 0; u--) {
rebuild_bridge(u);
}
}
int size() const { return n0; }
/// @brief Add slope*i+intercept to every a_i with i in [l, r).
void range_add(int l, int r, value_type k, value_type B) {
assert(0 <= l && l <= r && r <= n0);
if (l == r) {
return;
}
int lc = l + n;
int rc = r + n;
while (lc < rc) {
if (lc & 1) {
lz[lc] += line{k, B};
lc++;
}
lc >>= 1;
if (rc & 1) {
--rc;
lz[rc] += line{k, B};
}
rc >>= 1;
}
lc = l + n;
rc = r + n;
for (int dep = 1; dep <= h; dep++) {
if ((lc >> dep << dep) != lc) {
rebuild_bridge(lc >> dep);
}
if ((rc >> dep << dep) != rc) {
rebuild_bridge((rc - 1) >> dep);
}
}
}
/// @brief Return min(a_i) over the nonempty range [l, r).
value_type range_min(int l, int r) const {
assert(0 <= l && l < r && r <= n0);
int lc = l + n;
int rc = r + n;
value_type ans = std::numeric_limits<value_type>::max();
while (lc < rc) {
if (lc & 1) {
ans = std::min(ans, subtree_minimum(lc++));
}
lc >>= 1;
if (rc & 1) {
ans = std::min(ans, subtree_minimum(--rc));
}
rc >>= 1;
}
return ans;
}
private:
using wide_type = __int128_t;
struct point {
value_type x = 0;
value_type y = 0;
friend point operator-(point A, point rhs) {
return {A.x - rhs.x, A.y - rhs.y};
}
friend bool operator==(point A, point rhs) {
return A.x == rhs.x && A.y == rhs.y;
}
};
struct line {
value_type k = 0;
value_type B = 0;
line &operator+=(line rh0) {
k += rh0.k;
B += rh0.B;
return *this;
}
};
struct bridge {
point l;
point r;
};
int n0 = 0;
int n = 1;
int h = 0;
std::vector<point> a0;
std::vector<line> lz;
std::vector<bridge> br;
static wide_type cross(point A, point rhs) {
return wide_type(A.x) * rhs.y - wide_type(A.y) * rhs.x;
}
static point apply(point val, line add) {
val.y += val.x * add.k + add.B;
return val;
}
void rebuild_bridge(int u) {
if (u >= n) {
return;
}
line aa;
for (int fa = u; fa > 0; fa >>= 1) {
aa += lz[fa];
}
int lc = u * 2;
int rc = u * 2 + 1;
int lim = rc;
while (lim < n) {
lim <<= 1;
}
lim -= n;
line al = lz[lc];
line ar = lz[rc];
while (lc < n || rc < n) {
point a = apply(apply(br[lc].l, aa), al);
point b = apply(apply(br[lc].r, aa), al);
point c = apply(apply(br[rc].l, aa), ar);
point d = apply(apply(br[rc].r, aa), ar);
if (!(a == b) && cross(b - a, c - a) < 0) {
lc *= 2;
al += lz[lc];
} else if (!(c == d) && cross(c - b, d - b) < 0) {
rc = rc * 2 + 1;
ar += lz[rc];
} else if (a == b) {
rc *= 2;
ar += lz[rc];
} else if (c == d) {
lc = lc * 2 + 1;
al += lz[lc];
} else {
wide_type c1 = cross(b - a, d - c);
wide_type c2 = cross(b - a, b - c);
bool dir;
if (c1 == 0 && c2 == 0) {
dir = c.x < lim;
} else {
dir = wide_type(c.x) * c1 + wide_type(d.x - c.x) * c2 < c1 * lim;
}
if (dir) {
lc = lc * 2 + 1;
al += lz[lc];
} else {
rc *= 2;
ar += lz[rc];
}
}
}
br[u] = {apply(a0[lc], al), apply(a0[rc], ar)};
}
value_type subtree_minimum(int u) const {
line add;
for (int fa = u; fa > 0; fa >>= 1) {
add += lz[fa];
}
while (u < n) {
point l = apply(br[u].l, add);
point r = apply(br[u].r, add);
u = l.y < r.y ? u * 2 : u * 2 + 1;
add += lz[u];
}
return apply(a0[u], add).y;
}
};
} // namespace noya