Range Chmin Chmax Add Sum

data_structure/range_chmin_chmax_add_sum.hpp · GitHub で見る

共通ページ

#include "lib/data_structure/range_chmin_chmax_add_sum.hpp"

RangeChminChmaxAddSum seg(std::vector<long long>{1, 4, 2, 8});
seg.chmin(0, 4, 5);
seg.chmax(1, 3, 3);
seg.add(0, 2, 10);
seg.assign(2, 4, 7);
auto s = seg.sum(0, 4);
auto mn = seg.min(0, 4);
auto mx = seg.max(0, 4);

基本的な使い方の一覧

このヘッダーは chmin・chmax・加算・代入の専用版です。他の更新や集約値を定義する場合は 汎用版 を使ってください。

区間は \([l,r)\) です。RangeChminChmaxAddSum<T = long long, Sum = T> は符号付き整数を扱います。RangeChminChmaxAddSum<T, Sum>(n, x = 0) は長さ n を x で初期化します。和だけ広い型にする場合は RangeChminChmaxAddSum<long long, __int128_t> などを指定します。

操作	内容・返り値	計算量
RangeChminChmaxAddSum() / RangeChminChmaxAddSum(n,x = 0) / RangeChminChmaxAddSum(a)	空／同じ値の長さ n の列／配列から構築	空: \(O(1)\)、配列・長さ指定: \(O(n)\)
chmin(l,r,x)	各要素を \(\min(a_i,x)\) に更新	償却 \(O(\log^2 n)\)
chmax(l,r,x)	各要素を \(\max(a_i,x)\) に更新	償却 \(O(\log^2 n)\)
add(l,r,x) / assign(l,r,x)	区間への加算／代入	\(O(\log n)\)
sum(l,r) / min(l,r) / max(l,r)	区間和／最小値／最大値	\(O(\log n)\)
all_sum() / all_min() / all_max()	全体の和／最小値／最大値	\(O(1)\)
get(p) / set(p,x)	1 点の取得／代入	\(O(\log n)\)
values()	全要素を vector<T> で取得	\(O(n)\)
size()	要素数	\(O(1)\)

値は numeric_limits<T>::lowest() より大きく、numeric_limits<T>::max() より小さくしてください。値・累積加算は T、和・更新差分と個数の積は Sum に収まる必要があります。空区間の和は 0、最小値・最大値はそれぞれ numeric_limits<T>::max()・lowest() です。

構築・values()・空間は \(O(n)\)、add・assign・区間取得・get・set は \(O(\log n)\)、chmin・chmax を含む更新は償却 \(O(\log^2 n)\)、全体の取得・size() は \(O(1)\) です。

依存ライブラリ

• Default Init Allocator

検証コード

• test/range_chmin_chmax_add_sum.test.cpp

コード

#ifndef RANGE_CHMIN_CHMAX_ADD_SUM_HPP
#define RANGE_CHMIN_CHMAX_ADD_SUM_HPP

#include <algorithm>
#include <cassert>
#include <limits>
#include <type_traits>
#include <vector>
#include "../components/default_init_allocator.hpp"

template <class T = long long, class Sum = T>
class RangeChminChmaxAddSum {
	static_assert(std::is_integral_v<T> && std::is_signed_v<T>);
	static constexpr T inf = std::numeric_limits<T>::max();
	static constexpr T neg_inf = std::numeric_limits<T>::lowest();
	struct Node {
		Sum sum;
		T lo, hi, lo2, hi2, add;
		int nlo, nhi;
	};
	int n = 0;
	mutable std::vector<Node, DefaultInitAllocator<Node>> tree;
	static Node *left(Node *p) { return p + 1; }
	static Node *right(Node *p, int l, int m) { return p + 2 * (m - l); }
	static void fill(Node &a, T x, int len) {
		a = {Sum(x) * len, x, x, inf, neg_inf, 0, len, len};
	}
	static void add_node(Node &a, T x, int len) {
		a.sum += Sum(x) * len;
		a.lo += x;
		a.hi += x;
		if (a.lo2 != inf) a.lo2 += x;
		if (a.hi2 != neg_inf) a.hi2 += x;
		a.add += x;
	}
	static void lower(Node &a, T x) {
		a.sum += (Sum(x) - Sum(a.hi)) * a.nhi;
		if (a.lo == a.hi) a.lo = x;
		else if (a.lo2 == a.hi) a.lo2 = x;
		a.hi = x;
	}
	static void raise(Node &a, T x) {
		a.sum += (Sum(x) - Sum(a.lo)) * a.nlo;
		if (a.hi == a.lo) a.hi = x;
		else if (a.hi2 == a.lo) a.hi2 = x;
		a.lo = x;
	}
	static void pull(Node *p, Node *lc, Node *rc) {
		auto &a = *p;
		const auto &b = *lc, &c = *rc;
		a.sum = b.sum + c.sum;
		if (b.lo < c.lo) a.lo = b.lo, a.lo2 = std::min(b.lo2, c.lo), a.nlo = b.nlo;
		else if (b.lo > c.lo) a.lo = c.lo, a.lo2 = std::min(b.lo, c.lo2), a.nlo = c.nlo;
		else a.lo = b.lo, a.lo2 = std::min(b.lo2, c.lo2), a.nlo = b.nlo + c.nlo;
		if (b.hi > c.hi) a.hi = b.hi, a.hi2 = std::max(b.hi2, c.hi), a.nhi = b.nhi;
		else if (b.hi < c.hi) a.hi = c.hi, a.hi2 = std::max(b.hi, c.hi2), a.nhi = c.nhi;
		else a.hi = b.hi, a.hi2 = std::max(b.hi2, c.hi2), a.nhi = b.nhi + c.nhi;
	}
	static void push(Node *p, int l, int m, int r) {
		auto &a = *p, &b = *left(p), &c = *right(p, l, m);
		if (a.lo == a.hi) {
			fill(b, a.lo, m - l);
			fill(c, a.lo, r - m);
			a.add = 0;
			return;
		}
		if (a.add) {
			add_node(b, a.add, m - l);
			add_node(c, a.add, r - m);
			a.add = 0;
		}
		if (b.hi > a.hi) lower(b, a.hi);
		if (b.lo < a.lo) raise(b, a.lo);
		if (c.hi > a.hi) lower(c, a.hi);
		if (c.lo < a.lo) raise(c, a.lo);
	}
	template <class F>
	static void build(Node *p, int l, int r, const F &f) {
		if (r - l == 1) return fill(*p, f(l), 1);
		int m = (l + r) / 2;
		auto lc = left(p), rc = right(p, l, m);
		build(lc, l, m, f);
		build(rc, m, r, f);
		p->add = 0;
		pull(p, lc, rc);
	}
	template <int op>
	static void update(Node *p, int l, int r, int ql, int qr, T x) {
		auto &a = *p;
		if constexpr (op == 0) { if (a.hi <= x) return; }
		if constexpr (op == 1) { if (a.lo >= x) return; }
		if constexpr (op == 3) { if (a.lo == x && a.hi == x) return; }
		if (ql <= l && r <= qr) {
			if constexpr (op == 0) {
				if (x <= a.lo) return fill(a, x, r - l);
				if (a.hi2 < x) return lower(a, x);
			}
			if constexpr (op == 1) {
				if (x >= a.hi) return fill(a, x, r - l);
				if (a.lo2 > x) return raise(a, x);
			}
			if constexpr (op == 2) return add_node(a, x, r - l);
			if constexpr (op == 3) return fill(a, x, r - l);
		}
		int m = (l + r) / 2;
		auto lc = left(p), rc = right(p, l, m);
		push(p, l, m, r);
		if (ql < m) update<op>(lc, l, m, ql, qr, x);
		if (m < qr) update<op>(rc, m, r, ql, qr, x);
		pull(p, lc, rc);
	}
	template <int op>
	using Result = std::conditional_t<op == 0, Sum, T>;
	template <int op>
	static Result<op> query(Node *p, int l, int r, int ql, int qr) {
		const auto &a = *p;
		if (ql <= l && r <= qr) {
			if constexpr (op == 0) return a.sum;
			if constexpr (op == 1) return a.lo;
			if constexpr (op == 2) return a.hi;
		}
		if (a.lo == a.hi) {
			if constexpr (op == 0) return Sum(a.lo) * (std::min(r, qr) - std::max(l, ql));
			else return a.lo;
		}
		int m = (l + r) / 2;
		push(p, l, m, r);
		if (qr <= m) return query<op>(left(p), l, m, ql, qr);
		if (m <= ql) return query<op>(right(p, l, m), m, r, ql, qr);
		auto b = query<op>(left(p), l, m, ql, qr), c = query<op>(right(p, l, m), m, r, ql, qr);
		if constexpr (op == 0) return b + c;
		if constexpr (op == 1) return std::min(b, c);
		if constexpr (op == 2) return std::max(b, c);
	}
	static void collect(Node *p, int l, int r, std::vector<T> &a) {
		if (p->lo == p->hi) {
			std::fill(a.begin() + l, a.begin() + r, p->lo);
			return;
		}
		int m = (l + r) / 2;
		push(p, l, m, r);
		collect(left(p), l, m, a);
		collect(right(p, l, m), m, r, a);
	}
	void check(int l, int r) const { assert(0 <= l && l <= r && r <= n); (void)l; (void)r; }
public:
	RangeChminChmaxAddSum() = default;
	explicit RangeChminChmaxAddSum(int n, T x = 0) : n(n), tree(n > 0 ? 2 * std::size_t(n) - 1 : 0) {
		assert(n >= 0);
		if (n) build(tree.data(), 0, n, [x](int) { return x; });
	}
	explicit RangeChminChmaxAddSum(const std::vector<T> &a) : n(int(a.size())), tree(n ? 2 * std::size_t(n) - 1 : 0) {
		if (n) build(tree.data(), 0, n, [&](int i) { return a[i]; });
	}
	int size() const { return n; }
	void chmin(int l, int r, T x) { check(l, r); if (l < r) update<0>(tree.data(), 0, n, l, r, x); }
	void chmax(int l, int r, T x) { check(l, r); if (l < r) update<1>(tree.data(), 0, n, l, r, x); }
	void add(int l, int r, T x) { check(l, r); if (l < r && x) update<2>(tree.data(), 0, n, l, r, x); }
	void assign(int l, int r, T x) { check(l, r); if (l < r) update<3>(tree.data(), 0, n, l, r, x); }
	Sum sum(int l, int r) const { check(l, r); return l < r ? query<0>(tree.data(), 0, n, l, r) : Sum(0); }
	T min(int l, int r) const { check(l, r); return l < r ? query<1>(tree.data(), 0, n, l, r) : inf; }
	T max(int l, int r) const { check(l, r); return l < r ? query<2>(tree.data(), 0, n, l, r) : neg_inf; }
	Sum all_sum() const { return n ? tree[0].sum : Sum(0); }
	T all_min() const { return n ? tree[0].lo : inf; }
	T all_max() const { return n ? tree[0].hi : neg_inf; }
	T get(int p) const { assert(0 <= p && p < n); return min(p, p + 1); }
	void set(int p, T x) { assert(0 <= p && p < n); assign(p, p + 1, x); }
	std::vector<T> values() const {
		std::vector<T> a(n);
		if (n) collect(tree.data(), 0, n, a);
		return a;
	}
};

#endif

Back to top page