range_linear_add_range_min.hpp¶
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.
Verified by range_linear_add_range_min.
给区间加入关于下标的一次函数，并查询区间最小值；适合斜率更新与区间最值同时出现的题目。
Implementation¶
#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> &values) {
build(values);
}
void build(const std::vector<value_type> &values) {
length_ = int(values.size());
size_ = 1;
height_ = 0;
while (size_ < std::max(1, length_)) {
size_ <<= 1;
height_++;
}
base_.resize(2 * size_);
lazy_.assign(2 * size_, {});
bridge_.resize(2 * size_);
constexpr value_type infinity =
std::numeric_limits<value_type>::max() / 4;
for (int index = 0; index < size_; index++) {
value_type value = index < length_ ? values[index] : infinity;
base_[size_ + index] = {index, value};
bridge_[size_ + index] = {base_[size_ + index],
base_[size_ + index]};
}
for (int node = size_ - 1; node > 0; node--) {
rebuild_bridge(node);
}
}
int size() const { return length_; }
/// @brief Add slope*i+intercept to every a_i with i in [left, right).
void range_add(int left, int right, value_type slope,
value_type intercept) {
assert(0 <= left && left <= right && right <= length_);
if (left == right) {
return;
}
int left_node = left + size_;
int right_node = right + size_;
while (left_node < right_node) {
if (left_node & 1) {
lazy_[left_node] += line{slope, intercept};
left_node++;
}
left_node >>= 1;
if (right_node & 1) {
--right_node;
lazy_[right_node] += line{slope, intercept};
}
right_node >>= 1;
}
left_node = left + size_;
right_node = right + size_;
for (int level = 1; level <= height_; level++) {
if ((left_node >> level << level) != left_node) {
rebuild_bridge(left_node >> level);
}
if ((right_node >> level << level) != right_node) {
rebuild_bridge((right_node - 1) >> level);
}
}
}
/// @brief Return min(a_i) over the nonempty range [left, right).
value_type range_min(int left, int right) const {
assert(0 <= left && left < right && right <= length_);
int left_node = left + size_;
int right_node = right + size_;
value_type answer = std::numeric_limits<value_type>::max();
while (left_node < right_node) {
if (left_node & 1) {
answer = std::min(answer, subtree_minimum(left_node++));
}
left_node >>= 1;
if (right_node & 1) {
answer = std::min(answer, subtree_minimum(--right_node));
}
right_node >>= 1;
}
return answer;
}
private:
using wide_type = __int128_t;
struct point {
value_type x = 0;
value_type y = 0;
friend point operator-(point first, point second) {
return {first.x - second.x, first.y - second.y};
}
friend bool operator==(point first, point second) {
return first.x == second.x && first.y == second.y;
}
};
struct line {
value_type slope = 0;
value_type intercept = 0;
line &operator+=(line other) {
slope += other.slope;
intercept += other.intercept;
return *this;
}
};
struct bridge {
point left;
point right;
};
int length_ = 0;
int size_ = 1;
int height_ = 0;
std::vector<point> base_;
std::vector<line> lazy_;
std::vector<bridge> bridge_;
static wide_type cross(point first, point second) {
return wide_type(first.x) * second.y - wide_type(first.y) * second.x;
}
static point apply(point value, line addition) {
value.y += value.x * addition.slope + addition.intercept;
return value;
}
void rebuild_bridge(int node) {
if (node >= size_) {
return;
}
line ancestor_addition;
for (int ancestor = node; ancestor > 0; ancestor >>= 1) {
ancestor_addition += lazy_[ancestor];
}
int left_node = node * 2;
int right_node = node * 2 + 1;
int border = right_node;
while (border < size_) {
border <<= 1;
}
border -= size_;
line left_addition = lazy_[left_node];
line right_addition = lazy_[right_node];
while (left_node < size_ || right_node < size_) {
point a = apply(apply(bridge_[left_node].left, ancestor_addition),
left_addition);
point b = apply(apply(bridge_[left_node].right, ancestor_addition),
left_addition);
point c = apply(apply(bridge_[right_node].left, ancestor_addition),
right_addition);
point d = apply(apply(bridge_[right_node].right, ancestor_addition),
right_addition);
if (!(a == b) && cross(b - a, c - a) < 0) {
left_node *= 2;
left_addition += lazy_[left_node];
} else if (!(c == d) && cross(c - b, d - b) < 0) {
right_node = right_node * 2 + 1;
right_addition += lazy_[right_node];
} else if (a == b) {
right_node *= 2;
right_addition += lazy_[right_node];
} else if (c == d) {
left_node = left_node * 2 + 1;
left_addition += lazy_[left_node];
} else {
wide_type first_cross = cross(b - a, d - c);
wide_type second_cross = cross(b - a, b - c);
bool move_left;
if (first_cross == 0 && second_cross == 0) {
move_left = c.x < border;
} else {
move_left = wide_type(c.x) * first_cross +
wide_type(d.x - c.x) * second_cross <
first_cross * border;
}
if (move_left) {
left_node = left_node * 2 + 1;
left_addition += lazy_[left_node];
} else {
right_node *= 2;
right_addition += lazy_[right_node];
}
}
}
bridge_[node] = {apply(base_[left_node], left_addition),
apply(base_[right_node], right_addition)};
}
value_type subtree_minimum(int node) const {
line addition;
for (int ancestor = node; ancestor > 0; ancestor >>= 1) {
addition += lazy_[ancestor];
}
while (node < size_) {
point left = apply(bridge_[node].left, addition);
point right = apply(bridge_[node].right, addition);
node = left.y < right.y ? node * 2 : node * 2 + 1;
addition += lazy_[node];
}
return apply(base_[node], addition).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> &values) {
build(values);
}
void build(const std::vector<value_type> &values) {
length_ = int(values.size());
size_ = 1;
height_ = 0;
while (size_ < std::max(1, length_)) {
size_ <<= 1;
height_++;
}
base_.resize(2 * size_);
lazy_.assign(2 * size_, {});
bridge_.resize(2 * size_);
constexpr value_type infinity =
std::numeric_limits<value_type>::max() / 4;
for (int index = 0; index < size_; index++) {
value_type value = index < length_ ? values[index] : infinity;
base_[size_ + index] = {index, value};
bridge_[size_ + index] = {base_[size_ + index],
base_[size_ + index]};
}
for (int node = size_ - 1; node > 0; node--) {
rebuild_bridge(node);
}
}
int size() const { return length_; }
/// @brief Add slope*i+intercept to every a_i with i in [left, right).
void range_add(int left, int right, value_type slope,
value_type intercept) {
assert(0 <= left && left <= right && right <= length_);
if (left == right) {
return;
}
int left_node = left + size_;
int right_node = right + size_;
while (left_node < right_node) {
if (left_node & 1) {
lazy_[left_node] += line{slope, intercept};
left_node++;
}
left_node >>= 1;
if (right_node & 1) {
--right_node;
lazy_[right_node] += line{slope, intercept};
}
right_node >>= 1;
}
left_node = left + size_;
right_node = right + size_;
for (int level = 1; level <= height_; level++) {
if ((left_node >> level << level) != left_node) {
rebuild_bridge(left_node >> level);
}
if ((right_node >> level << level) != right_node) {
rebuild_bridge((right_node - 1) >> level);
}
}
}
/// @brief Return min(a_i) over the nonempty range [left, right).
value_type range_min(int left, int right) const {
assert(0 <= left && left < right && right <= length_);
int left_node = left + size_;
int right_node = right + size_;
value_type answer = std::numeric_limits<value_type>::max();
while (left_node < right_node) {
if (left_node & 1) {
answer = std::min(answer, subtree_minimum(left_node++));
}
left_node >>= 1;
if (right_node & 1) {
answer = std::min(answer, subtree_minimum(--right_node));
}
right_node >>= 1;
}
return answer;
}
private:
using wide_type = __int128_t;
struct point {
value_type x = 0;
value_type y = 0;
friend point operator-(point first, point second) {
return {first.x - second.x, first.y - second.y};
}
friend bool operator==(point first, point second) {
return first.x == second.x && first.y == second.y;
}
};
struct line {
value_type slope = 0;
value_type intercept = 0;
line &operator+=(line other) {
slope += other.slope;
intercept += other.intercept;
return *this;
}
};
struct bridge {
point left;
point right;
};
int length_ = 0;
int size_ = 1;
int height_ = 0;
std::vector<point> base_;
std::vector<line> lazy_;
std::vector<bridge> bridge_;
static wide_type cross(point first, point second) {
return wide_type(first.x) * second.y - wide_type(first.y) * second.x;
}
static point apply(point value, line addition) {
value.y += value.x * addition.slope + addition.intercept;
return value;
}
void rebuild_bridge(int node) {
if (node >= size_) {
return;
}
line ancestor_addition;
for (int ancestor = node; ancestor > 0; ancestor >>= 1) {
ancestor_addition += lazy_[ancestor];
}
int left_node = node * 2;
int right_node = node * 2 + 1;
int border = right_node;
while (border < size_) {
border <<= 1;
}
border -= size_;
line left_addition = lazy_[left_node];
line right_addition = lazy_[right_node];
while (left_node < size_ || right_node < size_) {
point a = apply(apply(bridge_[left_node].left, ancestor_addition),
left_addition);
point b = apply(apply(bridge_[left_node].right, ancestor_addition),
left_addition);
point c = apply(apply(bridge_[right_node].left, ancestor_addition),
right_addition);
point d = apply(apply(bridge_[right_node].right, ancestor_addition),
right_addition);
if (!(a == b) && cross(b - a, c - a) < 0) {
left_node *= 2;
left_addition += lazy_[left_node];
} else if (!(c == d) && cross(c - b, d - b) < 0) {
right_node = right_node * 2 + 1;
right_addition += lazy_[right_node];
} else if (a == b) {
right_node *= 2;
right_addition += lazy_[right_node];
} else if (c == d) {
left_node = left_node * 2 + 1;
left_addition += lazy_[left_node];
} else {
wide_type first_cross = cross(b - a, d - c);
wide_type second_cross = cross(b - a, b - c);
bool move_left;
if (first_cross == 0 && second_cross == 0) {
move_left = c.x < border;
} else {
move_left = wide_type(c.x) * first_cross +
wide_type(d.x - c.x) * second_cross <
first_cross * border;
}
if (move_left) {
left_node = left_node * 2 + 1;
left_addition += lazy_[left_node];
} else {
right_node *= 2;
right_addition += lazy_[right_node];
}
}
}
bridge_[node] = {apply(base_[left_node], left_addition),
apply(base_[right_node], right_addition)};
}
value_type subtree_minimum(int node) const {
line addition;
for (int ancestor = node; ancestor > 0; ancestor >>= 1) {
addition += lazy_[ancestor];
}
while (node < size_) {
point left = apply(bridge_[node].left, addition);
point right = apply(bridge_[node].right, addition);
node = left.y < right.y ? node * 2 : node * 2 + 1;
addition += lazy_[node];
}
return apply(base_[node], addition).y;
}
};
} // namespace noya