結果
問題 | No.749 クエリ全部盛り |
ユーザー |
![]() |
提出日時 | 2018-10-19 23:28:03 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
#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;}