library

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

View the Project on GitHub yuruhi/library

:heavy_check_mark: test/RangeUpdateRangeSum.test.cpp

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/all/DSL_2_I"
#include "./../DataStructure/LazySegmentTree.cpp"
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);

	int n, q;
	cin >> n >> q;
	RangeUpdateRangeSum<ll, ll> seg(vector(n, S_sum<ll>(0)));
	while (q--) {
		int com, l, r;
		cin >> com >> l >> r;
		if (com == 0) {
			ll x;
			cin >> x;
			seg.apply(l, r + 1, x);
		} else if (com == 1) {
			cout << seg.prod(l, r + 1).value << '\n';
		}
	}
}
#line 1 "test/RangeUpdateRangeSum.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/all/DSL_2_I"
#line 1 "atcoder/lazysegtree.hpp"



#line 1 "atcoder/internal_bit.hpp"



#ifdef _MSC_VER
#include <intrin.h>
#endif

namespace atcoder {

	namespace internal {

		// @param n `0 <= n`
		// @return minimum non-negative `x` s.t. `n <= 2**x`
		int ceil_pow2(int n) {
			int x = 0;
			while ((1U << x) < (unsigned int)(n))
				x++;
			return x;
		}

		// @param n `1 <= n`
		// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
		int bsf(unsigned int n) {
#ifdef _MSC_VER
			unsigned long index;
			_BitScanForward(&index, n);
			return index;
#else
			return __builtin_ctz(n);
#endif
		}

	}  // namespace internal

}  // namespace atcoder


#line 5 "atcoder/lazysegtree.hpp"
#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
namespace atcoder {

	template <class S, S (*op)(S, S), S (*e)(), class F, S (*mapping)(F, S),
	          F (*composition)(F, F), F (*id)()>
	struct lazy_segtree {
	public:
		lazy_segtree() : lazy_segtree(0) {}
		lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
		lazy_segtree(const std::vector<S>& v) : _n(int(v.size())) {
			log = internal::ceil_pow2(_n);
			size = 1 << log;
			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 operator[](int p) {
			return get(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 >> 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 operator()(int l, int r) {
			return prod(l, r);
		}

		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;
		}

		std::vector<S> to_a() {
			std::vector<S> res(_n);
			for (int i = 0; i < _n; ++i) {
				res[i] = get(i);
			}
			return res;
		}

	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();
		}
	};

}  // namespace atcoder


#line 4 "DataStructure/LazySegmentTree.cpp"
#include <limits>

namespace internal {
	template <class T> struct S_sum {
		T value, size;
		S_sum(T v, T s = 1) : value(v), size(s) {}
	};

	template <class S> constexpr S constant_min() {
		return std::numeric_limits<S>::min();
	}
	template <class S> constexpr S constant_max() {
		return std::numeric_limits<S>::max();
	}
	template <class S> constexpr S constant_zero() {
		return static_cast<S>(0);
	}
	template <class T> constexpr S_sum<T> constant_zero_sum() {
		return {0, 0};
	}

	template <class S> constexpr S op_max(S x, S y) {
		return std::max(x, y);
	}
	template <class S> constexpr S op_min(S x, S y) {
		return std::min(x, y);
	}
	template <class T> constexpr S_sum<T> op_sum(S_sum<T> x, S_sum<T> y) {
		return {x.value + y.value, x.size + y.size};
	}

	template <class S, class F> constexpr S mapping_add(F f, S x) {
		return f + x;
	}
	template <class T, class F> constexpr S_sum<T> mapping_add_sum(F f, S_sum<T> x) {
		return {x.value + f * x.size, x.size};
	}
	template <class S, class F> constexpr S mapping_update(F f, S x) {
		return f == constant_max<F>() ? x : f;
	}
	template <class T, class F> constexpr S_sum<T> mapping_update_sum(F f, S_sum<T> x) {
		if (f != constant_max<F>()) x.value = f * x.size;
		return x;
	}

	template <class F> constexpr F composition_add(F f, F g) {
		return f + g;
	}
	template <class F> constexpr F composition_update(F f, F g) {
		return f == constant_max<F>() ? g : f;
	}
}  // namespace internal

using internal::S_sum;

template <class S, class F>
using RangeAddRangeMax =
    atcoder::lazy_segtree<S, internal::op_max<S>, internal::constant_min<S>, F,
                          internal::mapping_add<S, F>, internal::composition_add<F>,
                          internal::constant_zero<F>>;
template <class S, class F>
using RangeAddRangeMin =
    atcoder::lazy_segtree<S, internal::op_min<S>, internal::constant_max<S>, F,
                          internal::mapping_add<S, F>, internal::composition_add<F>,
                          internal::constant_zero<F>>;
template <class T, class F>
using RangeAddRangeSum =
    atcoder::lazy_segtree<internal::S_sum<T>, internal::op_sum<T>,
                          internal::constant_zero_sum<T>, F, internal::mapping_add_sum<T, F>,
                          internal::composition_add<F>, internal::constant_zero<F>>;
template <class S, class F>
using RangeUpdateRangeMax =
    atcoder::lazy_segtree<S, internal::op_max<S>, internal::constant_min<S>, F,
                          internal::mapping_update<S, F>, internal::composition_update<F>,
                          internal::constant_max<F>>;
template <class S, class F>
using RangeUpdateRangeMin =
    atcoder::lazy_segtree<S, internal::op_min<S>, internal::constant_max<S>, F,
                          internal::mapping_update<S, F>, internal::composition_update<F>,
                          internal::constant_max<F>>;
template <class T, class F>
using RangeUpdateRangeSum =
    atcoder::lazy_segtree<internal::S_sum<T>, internal::op_sum<T>,
                          internal::constant_zero_sum<T>, F,
                          internal::mapping_update_sum<T, F>, internal::composition_update<F>,
                          internal::constant_max<F>>;
#line 5 "test/RangeUpdateRangeSum.test.cpp"
using namespace std;
using ll = long long;

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);

	int n, q;
	cin >> n >> q;
	RangeUpdateRangeSum<ll, ll> seg(vector(n, S_sum<ll>(0)));
	while (q--) {
		int com, l, r;
		cin >> com >> l >> r;
		if (com == 0) {
			ll x;
			cin >> x;
			seg.apply(l, r + 1, x);
		} else if (com == 1) {
			cout << seg.prod(l, r + 1).value << '\n';
		}
	}
}
Back to top page