Algorithms

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub HyunjaeLee/Algorithms

:heavy_check_mark: test/segtree_beats.test.cpp

Depends on

Code

#define PROBLEM                                                                \
    "https://judge.yosupo.jp/problem/range_chmin_chmax_add_range_sum"

#include "../segment_tree/segtree_beats.hpp"
#include <bits/stdc++.h>

struct S {
    long long max, max2, min, min2, sum;
    int max_count, min_count, size;
};

struct F {
    long long upper, lower, sum;
};

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    int N, Q;
    std::cin >> N >> Q;
    std::vector<S> v(N);
    constexpr auto inf = static_cast<long long>(1e18);
    for (auto &s : v) {
        long long x;
        std::cin >> x;
        s.max = s.min = s.sum = x;
        s.max_count = s.min_count = s.size = 1;
        s.max2 = -inf;
        s.min2 = inf;
    }
    auto op = [](S a, S b) -> S {
        S ret{};
        if (a.max < b.max) {
            ret.max = b.max;
            ret.max2 = std::max(a.max, b.max2);
            ret.max_count = b.max_count;
        } else if (b.max < a.max) {
            ret.max = a.max;
            ret.max2 = std::max(a.max2, b.max);
            ret.max_count = a.max_count;
        } else {
            ret.max = a.max;
            ret.max2 = std::max(a.max2, b.max2);
            ret.max_count = a.max_count + b.max_count;
        }
        if (a.min < b.min) {
            ret.min = a.min;
            ret.min2 = std::min(a.min2, b.min);
            ret.min_count = a.min_count;
        } else if (b.min < a.min) {
            ret.min = b.min;
            ret.min2 = std::min(a.min, b.min2);
            ret.min_count = b.min_count;
        } else {
            ret.min = a.min;
            ret.min2 = std::min(a.min2, b.min2);
            ret.min_count = a.min_count + b.min_count;
        }
        ret.sum = a.sum + b.sum;
        ret.size = a.size + b.size;
        return ret;
    };
    auto e = []() -> S { return {-inf, -inf, inf, inf, 0, 0, 0, 0}; };
    auto mapping = [](F f, S x) -> std::pair<S, bool> {
        x.max += f.sum;
        x.max2 += f.sum;
        x.min += f.sum;
        x.min2 += f.sum;
        x.sum += f.sum * x.size;
        if (x.max <= f.lower) {
            return {{f.lower, -1, f.lower, -1, f.lower * x.size, x.size, x.size,
                     x.size},
                    true};
        }
        if (f.upper <= x.min) {
            return {{f.upper, -1, f.upper, -1, f.upper * x.size, x.size, x.size,
                     x.size},
                    true};
        }
        if (x.max2 < f.upper && f.upper < x.max) {
            x.sum -= (x.max - f.upper) * x.max_count;
            x.max = f.upper;
        } else if (f.upper <= x.max2) {
            return {x, false};
        }
        if (x.max < x.min) {
            x.min = x.max;
        } else if (x.max < x.min2) {
            x.min2 = x.max;
        }
        if (x.min < f.lower && f.lower < x.min2) {
            x.sum += (f.lower - x.min) * x.min_count;
            x.min = f.lower;
        } else if (x.min2 <= f.lower) {
            return {x, false};
        }
        if (x.max < x.min) {
            x.max = x.min;
        } else if (x.max2 < x.min) {
            x.max2 = x.min;
        }
        return {x, true};
    };
    auto composition = [](F f, F g) -> F {
        g.upper += f.sum;
        g.lower += f.sum;
        g.sum += f.sum;
        g.upper = std::min(f.upper, g.upper);
        if (g.upper < g.lower) {
            g.lower = g.upper;
        }
        g.lower = std::max(f.lower, g.lower);
        if (g.upper < g.lower) {
            g.upper = g.lower;
        }
        return g;
    };
    auto id = []() -> F { return {inf, -inf, 0}; };
    segtree_beats seg(v, op, e, mapping, composition, id);
    for (auto i = 0; i < Q; ++i) {
        int q, l, r;
        std::cin >> q >> l >> r;
        auto b = 0LL;
        if (q != 3)
            std::cin >> b;
        switch (q) {
        case 0:
            seg.apply(l, r, {b, -inf, 0});
            break;
        case 1:
            seg.apply(l, r, {inf, b, 0});
            break;
        case 2:
            seg.apply(l, r, {inf, -inf, b});
            break;
        case 3:
            std::cout << seg.prod(l, r).sum << '\n';
            break;
        }
    }
}
#line 1 "test/segtree_beats.test.cpp"
#define PROBLEM                                                                \
    "https://judge.yosupo.jp/problem/range_chmin_chmax_add_range_sum"

#line 1 "segment_tree/segtree_beats.hpp"



#include <algorithm>
#include <cassert>
#include <tuple>
#include <vector>

template <typename S, typename Op, typename E, typename F, typename Mapping,
          typename Composition, typename Id>
struct segtree_beats {
    segtree_beats(const std::vector<S> &data, Op op, E e, Mapping mapping,
                  Composition composition, Id id)
        : op_(op), e_(e), mapping_(mapping), composition_(composition), id_(id),
          n_(static_cast<int>(data.size())),
          log_(std::__lg(std::max(n_ - 1, 1)) + 1), size_(1 << log_),
          data_(2 * size_, e_()), lazy_(size_, id_()) {
        for (auto i = 0; i < n_; ++i) {
            data_[size_ + i] = data[i];
        }
        for (auto i = size_ - 1; i >= 1; --i) {
            update(i);
        }
    }
    void set(int pos, S x) {
        assert(0 <= pos && pos < n_);
        pos += size_;
        for (auto i = log_; i >= 1; --i) {
            push(pos >> i);
        }
        data_[pos] = x;
        for (auto i = 1; i <= log_; ++i) {
            update(pos >> i);
        }
    }
    S get(int pos) {
        assert(0 <= pos && pos < n_);
        pos += size_;
        for (auto i = log_; i >= 1; --i) {
            push(pos >> i);
        }
        return data_[pos];
    }
    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= n_);
        if (l == r)
            return e_();
        l += size_;
        r += size_;
        for (auto 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, data_[l++]);
            }
            if (r & 1) {
                smr = op_(data_[--r], smr);
            }
            l >>= 1;
            r >>= 1;
        }
        return op_(sml, smr);
    }
    S all_prod() { return data_[1]; }
    void apply(int pos, F f) {
        assert(0 <= pos && pos < n_);
        pos += size_;
        for (auto i = log_; i >= 1; --i) {
            push(pos >> i);
        }
        auto ok = false;
        std::tie(data_[pos], ok) = mapping(f, data_[pos]);
        assert(ok);
        for (auto i = 1; i <= log_; ++i) {
            update(pos >> 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 (auto 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 (auto i = 1; i <= log_; ++i) {
            if (((l >> i) << i) != l) {
                update(l >> i);
            }
            if (((r >> i) << i) != r) {
                update((r - 1) >> i);
            }
        }
    }

private:
    void update(int node) {
        data_[node] = op_(data_[2 * node], data_[2 * node + 1]);
    }
    void all_apply(int node, F f) {
        auto ok = false;
        std::tie(data_[node], ok) = mapping_(f, data_[node]);
        if (node < size_) {
            lazy_[node] = composition_(f, lazy_[node]);
            if (!ok) {
                push(node);
                update(node);
            }
        }
    }
    void push(int node) {
        all_apply(2 * node, lazy_[node]);
        all_apply(2 * node + 1, lazy_[node]);
        lazy_[node] = id_();
    }
    Op op_;
    E e_;
    Mapping mapping_;
    Composition composition_;
    Id id_;
    const int n_, log_, size_;
    std::vector<S> data_;
    std::vector<F> lazy_;
};

template <typename S, typename Op, typename E, typename Mapping,
          typename Composition, typename Id>
segtree_beats(const std::vector<S> &data, Op op, E e, Mapping mapping,
              Composition composition, Id id)
    -> segtree_beats<S, Op, E, std::invoke_result_t<Id>, Mapping, Composition,
                     Id>;


#line 5 "test/segtree_beats.test.cpp"
#include <bits/stdc++.h>

struct S {
    long long max, max2, min, min2, sum;
    int max_count, min_count, size;
};

struct F {
    long long upper, lower, sum;
};

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    int N, Q;
    std::cin >> N >> Q;
    std::vector<S> v(N);
    constexpr auto inf = static_cast<long long>(1e18);
    for (auto &s : v) {
        long long x;
        std::cin >> x;
        s.max = s.min = s.sum = x;
        s.max_count = s.min_count = s.size = 1;
        s.max2 = -inf;
        s.min2 = inf;
    }
    auto op = [](S a, S b) -> S {
        S ret{};
        if (a.max < b.max) {
            ret.max = b.max;
            ret.max2 = std::max(a.max, b.max2);
            ret.max_count = b.max_count;
        } else if (b.max < a.max) {
            ret.max = a.max;
            ret.max2 = std::max(a.max2, b.max);
            ret.max_count = a.max_count;
        } else {
            ret.max = a.max;
            ret.max2 = std::max(a.max2, b.max2);
            ret.max_count = a.max_count + b.max_count;
        }
        if (a.min < b.min) {
            ret.min = a.min;
            ret.min2 = std::min(a.min2, b.min);
            ret.min_count = a.min_count;
        } else if (b.min < a.min) {
            ret.min = b.min;
            ret.min2 = std::min(a.min, b.min2);
            ret.min_count = b.min_count;
        } else {
            ret.min = a.min;
            ret.min2 = std::min(a.min2, b.min2);
            ret.min_count = a.min_count + b.min_count;
        }
        ret.sum = a.sum + b.sum;
        ret.size = a.size + b.size;
        return ret;
    };
    auto e = []() -> S { return {-inf, -inf, inf, inf, 0, 0, 0, 0}; };
    auto mapping = [](F f, S x) -> std::pair<S, bool> {
        x.max += f.sum;
        x.max2 += f.sum;
        x.min += f.sum;
        x.min2 += f.sum;
        x.sum += f.sum * x.size;
        if (x.max <= f.lower) {
            return {{f.lower, -1, f.lower, -1, f.lower * x.size, x.size, x.size,
                     x.size},
                    true};
        }
        if (f.upper <= x.min) {
            return {{f.upper, -1, f.upper, -1, f.upper * x.size, x.size, x.size,
                     x.size},
                    true};
        }
        if (x.max2 < f.upper && f.upper < x.max) {
            x.sum -= (x.max - f.upper) * x.max_count;
            x.max = f.upper;
        } else if (f.upper <= x.max2) {
            return {x, false};
        }
        if (x.max < x.min) {
            x.min = x.max;
        } else if (x.max < x.min2) {
            x.min2 = x.max;
        }
        if (x.min < f.lower && f.lower < x.min2) {
            x.sum += (f.lower - x.min) * x.min_count;
            x.min = f.lower;
        } else if (x.min2 <= f.lower) {
            return {x, false};
        }
        if (x.max < x.min) {
            x.max = x.min;
        } else if (x.max2 < x.min) {
            x.max2 = x.min;
        }
        return {x, true};
    };
    auto composition = [](F f, F g) -> F {
        g.upper += f.sum;
        g.lower += f.sum;
        g.sum += f.sum;
        g.upper = std::min(f.upper, g.upper);
        if (g.upper < g.lower) {
            g.lower = g.upper;
        }
        g.lower = std::max(f.lower, g.lower);
        if (g.upper < g.lower) {
            g.upper = g.lower;
        }
        return g;
    };
    auto id = []() -> F { return {inf, -inf, 0}; };
    segtree_beats seg(v, op, e, mapping, composition, id);
    for (auto i = 0; i < Q; ++i) {
        int q, l, r;
        std::cin >> q >> l >> r;
        auto b = 0LL;
        if (q != 3)
            std::cin >> b;
        switch (q) {
        case 0:
            seg.apply(l, r, {b, -inf, 0});
            break;
        case 1:
            seg.apply(l, r, {inf, b, 0});
            break;
        case 2:
            seg.apply(l, r, {inf, -inf, b});
            break;
        case 3:
            std::cout << seg.prod(l, r).sum << '\n';
            break;
        }
    }
}
Back to top page