#592172 (C++17) No.1234 典型RMQ

提出ソース

結果

問題	No.1234 典型RMQ
ユーザー	kya_ski
提出日時	2020-12-11 17:42:17
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	93 ms / 2,000 ms
コード長	4,635 bytes
コンパイル時間	968 ms
コンパイル使用メモリ	93,800 KB
実行使用メモリ	7,296 KB
最終ジャッジ日時	2024-04-26 11:45:54
合計ジャッジ時間	4,594 ms
ジャッジサーバーID （参考情報）	judge2 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	1 ms 5,376 KB
testcase_05	AC	2 ms 5,376 KB
testcase_06	AC	87 ms 6,144 KB
testcase_07	AC	68 ms 5,376 KB
testcase_08	AC	93 ms 6,912 KB
testcase_09	AC	80 ms 5,376 KB
testcase_10	AC	90 ms 6,656 KB
testcase_11	AC	84 ms 5,888 KB
testcase_12	AC	77 ms 5,376 KB
testcase_13	AC	69 ms 5,376 KB
testcase_14	AC	78 ms 5,376 KB
testcase_15	AC	78 ms 5,376 KB
testcase_16	AC	90 ms 6,400 KB
testcase_17	AC	80 ms 5,376 KB
testcase_18	AC	62 ms 5,376 KB
testcase_19	AC	91 ms 6,944 KB
testcase_20	AC	65 ms 7,168 KB
testcase_21	AC	87 ms 5,888 KB
testcase_22	AC	71 ms 7,232 KB
testcase_23	AC	72 ms 7,296 KB
testcase_24	AC	73 ms 7,168 KB
testcase_25	AC	71 ms 7,216 KB
testcase_26	AC	71 ms 7,168 KB
testcase_27	AC	2 ms 5,376 KB
testcase_28	AC	2 ms 5,376 KB
testcase_29	AC	2 ms 5,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <vector>
#include <functional>

template<class T, class E, class F, class G, class H>
struct lazy_segment_tree {
	using value_type = T;
	using operand_type = E;
	using size_type = std::size_t;
private :
	class node_type {
	public :
		value_type value;
		operand_type operand;
		node_type () = default;
		node_type (const value_type &value, const operand_type &operand)
		noexcept : value(value), operand(operand) { }
	};

	size_type n;
	const F f;
	const G g;
	const H h;
	const value_type value_identity;
	const operand_type operand_identity;
	std::vector<node_type> node;

	value_type reflect (const size_type &i) noexcept {
		if (node[i].operand == operand_identity) return node[i].value;
		return g(node[i].value, node[i].operand);
	}

	void merge (const size_type &i) noexcept {
		node[i].value = f(reflect(i << 1 | 0), reflect(i << 1 | 1));
	}

	void add (const size_type &i, const operand_type &operand) noexcept {
		node[i].operand = h(node[i].operand, operand);
	}

	void propagate (size_type i) noexcept {
		if (node[i].operand == operand_identity) return;
		add(i << 1 | 0, node[i].operand);
		add(i << 1 | 1, node[i].operand);
		node[i].value = reflect(i);
		node[i].operand = operand_identity;
	}

	void topdown_update (size_type i) noexcept {
		if (i == 0) return;
		for (size_type h = 32 - __builtin_clz(i); h; h--) {
			propagate(i >> h);
		}
	}

	void bottomup_update (size_type i) noexcept {
		if (i == 0) return;
		for (i >>= 1; i > 0; i >>= 1) {
			merge(i);
		}
	}

public :
	lazy_segment_tree (const value_type &value_identity, const operand_type &operand_identity, const F &f, const G &g, const H &h)
	noexcept : value_identity(value_identity), operand_identity(operand_identity), f(f), g(g), h(h) { }

	void assign (size_type _size) noexcept {
		n = _size;
		node.assign(_size << 1, node_type(value_identity, operand_identity));
	}

	void assign(size_type _size, const value_type &value) noexcept {
		assign(_size);
		for (size_type i = n; i < node.size(); i++) node[i].value = value;
		for (size_type i = n; i --> 0;) merge(i);
	}

	template<class InputIterator>
	void assign (InputIterator first, InputIterator last) noexcept {
		assign(last - first);
		for (size_type i = n; first != last; first++, i++) node[i].value = (*first);
		for (size_type i = n; i --> 0;) merge(i);
	}

	void update (size_type first, size_type last, const operand_type &operand) noexcept {
		const size_type _first = first + n, _last = last + n - 1;
		topdown_update(_first);
		topdown_update(_last);
		for (first += n, last += n; first != last; first >>= 1, last >>= 1) {
			if (first & 1) add(first++, operand);
			if (last  & 1) add(--last,  operand);
		}
		bottomup_update(_first);
		bottomup_update(_last);
	}

	value_type fold (size_type first, size_type last) noexcept {
		topdown_update(first + n);
		topdown_update(last + n - 1);
		value_type left = value_identity, right = value_identity;
		for (first += n, last += n; first != last; first >>= 1, last >>= 1) {
			if (first & 1) left = f(left, reflect(first++));
			if (last & 1) right = f(reflect(--last), right);
		}
		return f(left, right);
	}

};

template<class InputIterator, class T, class E, class F, class G, class H>
lazy_segment_tree<T, E, F, G, H> make_lazysegtree (InputIterator first, InputIterator last, const T &value_identity, const E &operand_identity, const F &f, const G &g, const H &h) {
	lazy_segment_tree<T, E, F, G, H> tree(value_identity, operand_identity, f, g, h);
	tree.assign(first, last);
	return std::move(tree);
}

template<class T, class E, class F, class G, class H>
lazy_segment_tree<T, E, F, G, H> make_lazysegtree (const T &value_identity, const E &operand_identity, const F &f, const G &g, const H &h) {
	return lazy_segment_tree<T, E, F, G, H>(value_identity, operand_identity, f, g, h);
}


#include <iostream>
#include <cstdint>

using i64 = std::int64_t;

constexpr i64 infty = (1LL << 60);

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	size_t n;
	std::cin >> n;
	std::vector<i64> as(n);
	for (i64 &a : as) std::cin >> a;
	
	auto f = [](const i64 &lhs, const i64 &rhs) { return std::min(lhs, rhs); };
	auto g = [](const i64 &lhs, const i64 &rhs) { return (lhs == infty ? infty : lhs + rhs); };
	auto h = [](const i64 &lhs, const i64 &rhs) { return lhs + rhs; };
	auto seg = make_lazysegtree(as.begin(), as.end(), infty, 0LL, f, g, h);
	
	size_t q;
	std::cin >> q;
	for (size_t _ = 0; _ < q; _++) {
		size_t type, l, r;
		i64 value;
		std::cin >> type >> l >> r >> value;
		l--; r--;
		if (type == 1) seg.update(l, r + 1, value);
		else std::cout << seg.fold(l, r + 1) << '\n';
	}
	
	return 0;
}

yukicoder

結果

テストケース

ソースコード