結果

問題 No.749 クエリ全部盛り
ユーザー noshi91noshi91
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0