#293136 (C++14) No.749 クエリ全部盛り

提出ソース

結果

問題	No.749 クエリ全部盛り
ユーザー	noshi91
提出日時	2018-10-19 23:28:03
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	967 ms / 3,000 ms
コード長	8,935 bytes
コンパイル時間	1,118 ms
コンパイル使用メモリ	79,384 KB
実行使用メモリ	56,320 KB
最終ジャッジ日時	2024-11-18 22:41:35
合計ジャッジ時間	7,181 ms
ジャッジサーバーID （参考情報）	judge5 / judge2

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	2 ms 5,248 KB
testcase_03	AC	2 ms 5,248 KB
testcase_04	AC	2 ms 5,248 KB
testcase_05	AC	4 ms 5,248 KB
testcase_06	AC	4 ms 5,248 KB
testcase_07	AC	4 ms 5,248 KB
testcase_08	AC	4 ms 5,248 KB
testcase_09	AC	4 ms 5,248 KB
testcase_10	AC	31 ms 5,248 KB
testcase_11	AC	30 ms 5,248 KB
testcase_12	AC	31 ms 5,248 KB
testcase_13	AC	31 ms 5,248 KB
testcase_14	AC	31 ms 5,248 KB
testcase_15	AC	955 ms 56,280 KB
testcase_16	AC	964 ms 56,316 KB
testcase_17	AC	967 ms 56,236 KB
testcase_18	AC	956 ms 56,212 KB
testcase_19	AC	954 ms 56,320 KB

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

ソースコード

raw source code

#include <cassert>
#include <iterator>
#include <stdexcept>
#include <utility>

template <class ValueMonoid, class OperatorMonoid, class Modifier,
	template <class> class Container>
class lazy_segment_tree {
public:
	using value_structure = ValueMonoid;
	using value_type = typename value_structure::value_type;
	using const_reference = const value_type &;
	using operator_structure = OperatorMonoid;
	using operator_type = typename operator_structure::value_type;
	using modifier = Modifier;
	using container_type = Container<::std::pair<value_type, operator_type>>;
	using size_type = typename container_type::size_type;

private:
	size_type size_, height;
	container_type tree;
	static size_type getheight(const size_type size) noexcept {
		size_type ret = 0;
		while (static_cast<size_type>(1) << ret < size)
			++ret;
		return ret;
	}
	static value_type reflect(typename container_type::const_reference element) {
		return modifier::operation(element.first, element.second);
	}
	void recalc(const size_type index) {
		tree[index].first = value_structure::operation(
			reflect(tree[index << 1]), reflect(tree[index << 1 | 1]));
	}
	static void assign(operator_type &element, const operator_type &data) {
		element = operator_structure::operation(element, data);
	}
	void push(const size_type index) {
		assign(tree[index << 1].second, tree[index].second);
		assign(tree[index << 1 | 1].second, tree[index].second);
		tree[index].second = operator_structure::identity();
	}
	void propagate(const size_type index) {
		for (size_type i = height; i; --i)
			push(index >> i);
	}
	void thrust(const size_type index) {
		tree[index].first = reflect(tree[index]);
		push(index);
	}
	void evaluate(const size_type index) {
		for (size_type i = height; i; --i)
			thrust(index >> i);
	}
	void build(size_type index) {
		while (index >>= 1)
			recalc(index);
	}
	size_type base_size() const { return static_cast<size_type>(1) << height; }

public:
	lazy_segment_tree() : size_(0), height(0), tree() {}
	explicit lazy_segment_tree(const size_type size)
		: size_(size), height(getheight(size_)),
		tree(static_cast<size_type>(1) << (height + 1),
		{ value_structure::identity(), operator_structure::identity() }) {}
	template <class InputIterator>
	explicit lazy_segment_tree(InputIterator first, InputIterator last)
		: size_(::std::distance(first, last)), height(getheight(size_)), tree() {
		const size_type cap = static_cast<size_type>(1) << height;
		tree.reserve(cap << 1);
		tree.resize(cap,
		{ value_structure::identity(), operator_structure::identity() });
		for (; first != last; ++first)
			tree.emplace_back(*first, operator_structure::identity());
		tree.resize(cap << 1,
		{ value_structure::identity(), operator_structure::identity() });
		for (size_type i = cap - 1; i; --i)
			recalc(i);
	}

	bool empty() const { return !size_; }
	size_type size() const { return size_; }

	const_reference operator[](size_type index) {
		assert(index < size());
		index += base_size();
		evaluate(index);
		tree[index].first = reflect(tree[index]);
		tree[index].second = operator_structure::identity();
		return tree[index].first;
	}
	const_reference at(size_type index) {
		if (index < size()) {
			throw ::std::out_of_range("index out of range");
		}
		else {
			index += base_size();
			evaluate(index);
			tree[index].first = reflect(tree[index]);
			tree[index].second = operator_structure::identity();
			return tree[index].first;
		}
	}
	value_type fold(size_type first, size_type last) {
		assert(first <= last);
		assert(first <= size());
		assert(last <= size());
		first += base_size();
		last += base_size();
		evaluate(first);
		evaluate(last - 1);
		value_type ret_l = value_structure::identity(),
			ret_r = value_structure::identity();
		for (; first < last; first >>= 1, last >>= 1) {
			if (first & 1)
				ret_l = value_structure::operation(ret_l, reflect(tree[first++]));
			if (last & 1)
				ret_r = value_structure::operation(reflect(tree[last - 1]), ret_r);
		}
		return value_structure::operation(ret_l, ret_r);
	}
	template <class F> size_type search(const F &f) {
		if (f(value_structure::identity()))
			return static_cast<size_type>(0);
		if (!f(reflect(tree[1])))
			return size() + 1;
		value_type acc = value_structure::identity();
		size_type i = 1;
		while (i < base_size()) {
			thrust(i);
			if (!f(value_structure::operation(acc, reflect(tree[i <<= 1]))))
				acc = value_structure::operation(acc, reflect(tree[i++]));
		}
		return i - base_size() + 1;
	}

	template <class F> void update(size_type index, const F &f) {
		assert(index < size());
		index += base_size();
		propagate(index);
		tree[index].first = f(reflect(tree[index]));
		tree[index].second = operator_structure::identity();
		build(index);
	}
	void update(size_type first, size_type last, const operator_type &data) {
		assert(first <= last);
		assert(first <= size());
		assert(last <= size());
		first += base_size();
		last += base_size();
		propagate(first);
		propagate(last - 1);
		for (size_type left = first, right = last; left < right;
			left >>= 1, right >>= 1) {
			if (left & 1)
				assign(tree[left++].second, data);
			if (right & 1)
				assign(tree[right - 1].second, data);
		}
		build(first);
		build(last - 1);
	}
};

#include <cstdint>

template <::std::uint_least32_t MODULO> class modint {
	using u32 = ::std::uint_least32_t;
	using u64 = ::std::uint_least64_t;

public:
	using value_type = u32;
	u32 a;
	modint() noexcept : a(0) {}
	modint(const u32 x) noexcept : a(x) {}
	u32 value() const noexcept { return a; }
	modint operator+(const modint &o) const noexcept {
		return a + o.a < MODULO ? modint(a + o.a) : modint(a + o.a - MODULO);
	}
	modint operator-(const modint &o) const noexcept {
		return modint(a < o.a ? a + MODULO - o.a : a - o.a);
	}
	modint operator*(const modint &o) const noexcept {
		return modint(static_cast<u64>(a) * o.a % MODULO);
	}
	modint operator/(const modint &o) const {
		return modint(static_cast<u64>(a) * (~o).a % MODULO);
	}
	modint &operator+=(const modint &o) noexcept {
		if (a += o.a >= MODULO)
			a -= MODULO;
		return *this;
	}
	modint &operator-=(const modint &o) noexcept {
		if (a < o.a)
			a += MODULO;
		a -= o.a;
		return *this;
	}
	modint &operator*=(const modint &o) noexcept {
		a = static_cast<u64>(a) * o.a % MODULO;
		return *this;
	}
	modint &operator/=(const modint &o) {
		a = static_cast<u64>(a) * (~o).a % MODULO;
		return *this;
	}
	modint operator~() const noexcept { return pow(MODULO - 2); }
	modint operator-() const noexcept { return a ? modint(MODULO - a) : *this; }
	modint operator++() noexcept { return a == MODULO - 1 ? a = 0 : ++a, *this; }
	modint operator--() noexcept { return a ? --a : a = MODULO - 1, *this; }
	bool operator==(const modint &o) const noexcept { return a == o.a; }
	bool operator!=(const modint &o) const noexcept { return a != o.a; }
	bool operator<(const modint &o) const noexcept { return a < o.a; }
	bool operator<=(const modint &o) const noexcept { return a <= o.a; }
	bool operator>(const modint &o) const noexcept { return a > o.a; }
	bool operator>=(const modint &o) const noexcept { return a >= o.a; }
	explicit operator bool() const noexcept { return a; }
	explicit operator u32() const noexcept { return a; }
	modint pow(u32 x) const noexcept {
		u64 t = a, u = 1;
		while (x) {
			if (x & 1)
				u = u * t % MODULO;
			t = (t * t) % MODULO;
			x >>= 1;
		}
		return modint(u);
	}
};

using mint = modint<1000000007>;

struct y749v {
	mint x, y, z;
};
struct y749o {
	mint a, b, c;
};

struct val {
	using value_type = y749v;
	static value_type operation(const value_type &l, const value_type &r) {
		return {
			l.x + r.x,
			l.y + r.y,
			l.z + r.z
		};
	}
	static value_type identity() {
		return { 0,0,0 };
	}
};

struct op {
	using value_type = y749o;
	static value_type operation(const value_type &l, const value_type &r) {
		return {
			l.a*r.a,
			l.b*r.a + r.b,
			l.c*r.a + r.c
		};
	}
	static value_type identity() {
		return { 1,0,0 };
	}
};

struct mod {
	static y749v operation(const y749v &l, const y749o &r) {
		return {
			l.x*r.a + l.y*r.b + l.z*r.c,
			l.y,
			l.z
		};
	}
};

#include<iostream>
#include<vector>
template<class T>using vec_alias = ::std::vector<T>;

int main() {
	int n, q;
	::std::cin >> n >> q;

	lazy_segment_tree<val, op, mod, vec_alias> seg(n);

	::std::vector<mint> fib(n);
	if (n > 1)
		fib[1] = 1;
	for (int i = 2;i < n;++i)
		fib[i] = fib[i - 1] + fib[i - 2];


	for (int i = 0;i < n;++i)
		seg.update(i, [&](const y749v &) {return y749v({ 0,1,fib[i] });});

	while (q--) {
		int t, l, r;
		mint k;
		::std::cin >> t >> l >> r >> k.a;
		++r;
		switch (t) {
		case 0:
			::std::cout << (seg.fold(l, r).x*k).a << ::std::endl;
			break;
		case 1:
			seg.update(l, r , { 0,k,0 });
			break;
		case 2:
			seg.update(l, r, { 1,k,0 });
			break;
		case 3:
			seg.update(l, r, { k,0,0 });
			break;
		case 4:
			seg.update(l, r, { 1,0,k });
			break;
		}
	}


	return 0;
}

yukicoder

結果

テストケース

ソースコード