lmori's Library
This documentation is automatically generated by competitive-verifier/competitive-verifier
Range Linear Add Range Sum
(data-structure/segment-tree/query/RangeLinearAddRangeSum.hpp)
- View this file on GitHub
- Last update: 2025-06-25 02:49:25+09:00
- Include:
#include "data-structure/segment-tree/query/RangeLinearAddRangeSum.hpp"
概要
todo
計算量
todo
Depends on
Lazy Segment Tree
(data-structure/segment-tree/LazySegmentTree.hpp)
Code
#include "../LazySegmentTree.hpp"
class RangeLinearAddRangeSum {
private:
static constexpr long long INF = 8e18;
static constexpr int INFI = int(1e9) + 10;
struct S {
long long sum;
int l, r;
};
struct F {
long long a, b;
};
static S op(S a, S b) {
return S{a.sum + b.sum, min(a.l, b.l), max(a.r, b.r)};
}
static S e() {
return S{0, INFI, -INFI};
}
static S mapping(F f, S s) {
return {s.sum + (f.a * (s.l + s.r - 1) + f.b * 2) * (s.r - s.l) / 2, s.l, s.r};
}
static F composition(F f, F g) {
return {f.a + g.a, f.b + g.b};
}
static F id() {
return F{0, 0};
}
lazy_segtree<S, op, e, F, mapping, composition, id> seg;
public:
RangeLinearAddRangeSum(const vector<long long> &v) {
int n = int(v.size());
vector<S> tmp(n);
for (int i = 0; i < n; i++) {
tmp[i].l = i;
tmp[i].r = i + 1;
tmp[i].sum = v[i];
}
seg = lazy_segtree<S, op, e, F, mapping, composition, id>(tmp);
}
void set(int i, S x) {
seg.set(i, x);
}
S get(int i) {
return seg.get(i);
}
S all_prod() {
return seg.all_prod();
}
S prod(int l, int r) {
return seg.prod(l, r);
}
void apply(int l, int r, F f) {
seg.apply(l, r, F{f.a, f.b - f.a * get(l).l});
}
void apply(int i, F f) {
seg.apply(i, F{f.a, f.b - f.a * get(i).l});
}
template <bool (*g)(S)>
int max_right(int l) {
return seg.max_right(l, [](S x) { return g(x); });
}
template <bool (*g)(S)>
int min_left(int r) {
return seg.min_left(r, [](S x) { return g(x); });
}
};#line 1 "data-structure/segment-tree/LazySegmentTree.hpp"
template <class S,
auto op,
auto e,
class F,
auto mapping,
auto composition,
auto id>
struct lazy_segtree {
private:
unsigned int seg_bit_ceil(unsigned int n) {
unsigned int x = 1;
while (x < (unsigned int)(n)) x *= 2;
return x;
}
public:
static_assert(std::is_convertible_v<decltype(op), std::function<S(S, S)>>,
"op must work as S(S, S)");
static_assert(std::is_convertible_v<decltype(e), std::function<S()>>,
"e must work as S()");
static_assert(
std::is_convertible_v<decltype(mapping), std::function<S(F, S)>>,
"mapping must work as F(F, S)");
static_assert(
std::is_convertible_v<decltype(composition), std::function<F(F, F)>>,
"compostiion must work as F(F, F)");
static_assert(std::is_convertible_v<decltype(id), std::function<F()>>,
"id must work as F()");
lazy_segtree() : lazy_segtree(0) {}
explicit lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
explicit lazy_segtree(const std::vector<S>& v) : _n(int(v.size())) {
size = (int)seg_bit_ceil((unsigned int)(_n));
log = __builtin_ctz((unsigned int)size);
d = std::vector<S>(2 * size, e());
lz = std::vector<F>(size, id());
for (int i = 0; i < _n; i++) d[size + i] = v[i];
for (int i = size - 1; i >= 1; i--) {
update(i);
}
}
void set(int p, S x) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
d[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}
S get(int p) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
return d[p];
}
S prod(int l, int r) {
assert(0 <= l && l <= r && r <= _n);
if (l == r) return e();
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);
}
S sml = e(), smr = e();
while (l < r) {
if (l & 1) sml = op(sml, d[l++]);
if (r & 1) smr = op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return op(sml, smr);
}
S all_prod() { return d[1]; }
void apply(int p, F f) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
d[p] = mapping(f, d[p]);
for (int i = 1; i <= log; i++) update(p >> i);
}
void apply(int l, int r, F f) {
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) all_apply(l++, f);
if (r & 1) all_apply(--r, f);
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);
}
}
template <bool (*g)(S)>
int max_right(int l) {
return max_right(l, [](S x) { return g(x); });
}
template <class G>
int max_right(int l, G g) {
assert(0 <= l && l <= _n);
assert(g(e()));
if (l == _n) return _n;
l += size;
for (int i = log; i >= 1; i--) push(l >> i);
S sm = e();
do {
while (l % 2 == 0) l >>= 1;
if (!g(op(sm, d[l]))) {
while (l < size) {
push(l);
l = (2 * l);
if (g(op(sm, d[l]))) {
sm = op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = op(sm, d[l]);
l++;
} while ((l & -l) != l);
return _n;
}
template <bool (*g)(S)>
int min_left(int r) {
return min_left(r, [](S x) { return g(x); });
}
template <class G>
int min_left(int r, G g) {
assert(0 <= r && r <= _n);
assert(g(e()));
if (r == 0) return 0;
r += size;
for (int i = log; i >= 1; i--) push((r - 1) >> i);
S sm = e();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!g(op(d[r], sm))) {
while (r < size) {
push(r);
r = (2 * r + 1);
if (g(op(d[r], sm))) {
sm = op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
} while ((r & -r) != r);
return 0;
}
private:
int _n, size, log;
std::vector<S> d;
std::vector<F> lz;
void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
void all_apply(int k, F f) {
d[k] = mapping(f, d[k]);
if (k < size) lz[k] = composition(f, lz[k]);
}
void push(int k) {
all_apply(2 * k, lz[k]);
all_apply(2 * k + 1, lz[k]);
lz[k] = id();
}
};
#line 2 "data-structure/segment-tree/query/RangeLinearAddRangeSum.hpp"
class RangeLinearAddRangeSum {
private:
static constexpr long long INF = 8e18;
static constexpr int INFI = int(1e9) + 10;
struct S {
long long sum;
int l, r;
};
struct F {
long long a, b;
};
static S op(S a, S b) {
return S{a.sum + b.sum, min(a.l, b.l), max(a.r, b.r)};
}
static S e() {
return S{0, INFI, -INFI};
}
static S mapping(F f, S s) {
return {s.sum + (f.a * (s.l + s.r - 1) + f.b * 2) * (s.r - s.l) / 2, s.l, s.r};
}
static F composition(F f, F g) {
return {f.a + g.a, f.b + g.b};
}
static F id() {
return F{0, 0};
}
lazy_segtree<S, op, e, F, mapping, composition, id> seg;
public:
RangeLinearAddRangeSum(const vector<long long> &v) {
int n = int(v.size());
vector<S> tmp(n);
for (int i = 0; i < n; i++) {
tmp[i].l = i;
tmp[i].r = i + 1;
tmp[i].sum = v[i];
}
seg = lazy_segtree<S, op, e, F, mapping, composition, id>(tmp);
}
void set(int i, S x) {
seg.set(i, x);
}
S get(int i) {
return seg.get(i);
}
S all_prod() {
return seg.all_prod();
}
S prod(int l, int r) {
return seg.prod(l, r);
}
void apply(int l, int r, F f) {
seg.apply(l, r, F{f.a, f.b - f.a * get(l).l});
}
void apply(int i, F f) {
seg.apply(i, F{f.a, f.b - f.a * get(i).l});
}
template <bool (*g)(S)>
int max_right(int l) {
return seg.max_right(l, [](S x) { return g(x); });
}
template <bool (*g)(S)>
int min_left(int r) {
return seg.min_left(r, [](S x) { return g(x); });
}
};