結果
問題 | No.749 クエリ全部盛り |
ユーザー |
![]() |
提出日時 | 2018-10-19 23:37:00 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 651 ms / 3,000 ms |
コード長 | 7,611 bytes |
コンパイル時間 | 2,081 ms |
コンパイル使用メモリ | 189,152 KB |
実行使用メモリ | 167,444 KB |
最終ジャッジ日時 | 2024-11-18 22:47:23 |
合計ジャッジ時間 | 6,403 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define INF_LL (int64)1e18#define INF (int32)1e9#define REP(i, n) for(int64 i = 0;i < (n);i++)#define FOR(i, a, b) for(int64 i = (a);i < (b);i++)#define all(x) x.begin(),x.end()#define fs first#define sc secondusing int32 = int_fast32_t;using uint32 = uint_fast32_t;using int64 = int_fast64_t;using uint64 = uint_fast64_t;using PII = pair<int32, int32>;using PLL = pair<int64, int64>;const double eps = 1e-10;template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}template<class ValueMonoid, class OperatorMonoid, class Modifier,template<class...> class Container=::std::vector>class LazySegTree{public:using value_structure = ValueMonoid;using value_type = typename value_structure::value_type;using operator_structure = OperatorMonoid;using operator_type = typename operator_structure::value_type;using modifier = Modifier;using const_reference = const value_type &;using container_value_type = Container<value_type>;using container_operator_type = Container<operator_type>;using size_type = typename container_value_type::size_type;private:container_value_type tree;container_operator_type lazy;size_type size_, height;static size_type getsize(const size_type x){size_type ret = 1;while(ret < x)ret <<= 1;return ret;}static size_type getheight(const size_type x){size_type ret = 0;while((static_cast<size_type>(1) << ret) < x){ret++;}return ret;}inline static value_type calc(const value_type a, const value_type b){return value_structure::operation(a, b);}inline static void apply(operator_type &data, const operator_type a){data = operator_structure::operation(data, a);}inline static value_type reflect(const value_type v, const operator_type o){return modifier::operation(v, o);}void push(const size_type index){tree[index] = reflect(tree[index], lazy[index]);apply(lazy[index << 1], lazy[index]);apply(lazy[index << 1 | 1], lazy[index]);lazy[index] = operator_structure::identity();}void calc_node(const size_type index){if(tree.size() <= (index << 1 | 1)) return;assert(0 < index);tree[index] = calc(reflect(tree[index << 1], lazy[index << 1]),reflect(tree[index << 1 | 1], lazy[index << 1 | 1]));}void build(size_type index){while(index >>= 1){calc_node(index);}}void propagate(const size_type index){for(size_type shift = height; shift ; --shift){push(index >> shift);}}void rebuild(){for(size_type i = size_-1;i > 0;--i){calc_node(i);}}public:LazySegTree() : size_(0), height(0), tree(), lazy(){}LazySegTree(const size_type size): size_(size), height(getheight(size)),tree(size << 1, value_structure::initializer()),lazy(size << 1, operator_structure::identity()){rebuild();}template<class InputIterator>LazySegTree(InputIterator first, InputIterator last): size_(::std::distance(first, last)){height = getheight(size_);tree = container_value_type(size_, value_structure::identity());lazy = container_operator_type(size_ << 1, operator_structure::identity());tree.insert(tree.end(), first, last);rebuild();}size_type size() const { return size_; }const_reference operator[](const size_type k){assert(k < size_);propagate(k+size_);tree[k+size_] = reflect(tree[k+size_], lazy[k+size_]);lazy[k+size_] = operator_structure::identity();return tree[k+size_];}value_type query(size_type l, size_type r){assert(l <= r);assert(0 <= l && l < size_);assert(0 <= r && r <= size_);value_type retl = value_structure::identity(),retr = value_structure::identity();l += size_;r += size_;propagate(l);propagate(r-1);for(; l < r ; l >>= 1, r >>= 1){if(l&1){retl = calc(retl, reflect(tree[l], lazy[l]));l++;}if(r&1){r--;retr = calc(reflect(tree[r], lazy[r]), retr);}}return calc(retl, retr);}void update(size_type l, size_type r, const operator_type& data){assert(l <= r);assert(0 <= l && l < size_);assert(0 <= r && r <= size_);l += size_;r += size_;propagate(l);propagate(r - 1);for(size_type l_ = l, r_ = r; l_ < r_ ; l_ >>= 1, r_ >>= 1){if(l_ & 1) apply(lazy[l_++], data);if(r_ & 1) apply(lazy[--r_], data);}build(l);build(r - 1);}template<class F>void update(size_type index, const F& f){assert(0 <= index && index < size());index += size_;propagate(index);tree[index] = f(::std::move(tree[index]));lazy[index] = operator_structure::identity();build(index);}/*template<class F>size_type search(const F& f) const { // [0, result) is True and [0, result-1) is not.if(f(value_structure::identity()))return 0;if(!f(tree[1]))return size_+1;value_type acc = value_structure::identity();size_type i = 1;while(i <}*/};const int64 mod = 1e9+7;int64 gcd(int64 a, int64 b){if(b == 0) return a;return gcd(b, a%b);}vector<int64> fib;struct value{int64 v;int64 l, r;value():v(0), l(0), r(0){}value(int64 v_, int64 l_, int64 r_){v = v_; l = l_; r = r_;}const value operator+(const value& rhs) const{return value((v+rhs.v)%mod, l, rhs.r);};};class vmonoid{public:using value_type = value;static value_type identity(){return value(0, 0, 0);}static value_type initializer(){return value(0, 0, 0);}static value_type operation(const value_type& a, const value_type& b){return value((a.v+b.v)%mod, a.l, b.r);}};class omonoid{public:using value_type = tuple<int64, int64, int64, int64>;static value_type identity(){return value_type(0, 1, -1, 0);}static value_type operation(const value_type& a, const value_type& b){int64 a0, a1, a2, a3, b0, b1, b2, b3;tie(a0, a1, a2, a3) = a;tie(b0, b1, b2, b3) = b;//printf("(%lld %lld %lld), (%lld %lld %lld), ", a0, a1, a2, b0, b1, b2);if(b2 > -1){// printf("(%lld %lld %lld)\n", 0LL, 1LL, b2);return b;}//printf("(%lld %lld %lld)\n", a0*b1+b0, a1*b1, a2);return value_type((a0*b1%mod+b0)%mod, a1*b1%mod, a2, ((a3*b1)%mod+b3)%mod);}};class modifier{public:using vl = vmonoid::value_type;using op = omonoid::value_type;static vl operation(const vl& a, const op& b){int64 a0, a1, a2, a3;tie(a0, a1, a2, a3) = b;if(a2 > -1){return value(((a2*a1%mod+a0)%mod*(a.r-a.l)%mod+((fib[a.r]-fib[a.l]+mod)%mod)*a3%mod)%mod, a.l, a.r);}return value(((a.v*a1%mod+a0*(a.r-a.l)%mod)%mod+(fib[a.r]-fib[a.l]+mod)%mod*a3%mod)%mod, a.l, a.r);}};int32 N, Q;void init(){fib.resize(N+1, 0);fib[2] = 1;FOR(i, 3, N+1){fib[i] = fib[i-1]+fib[i-2];fib[i] %= mod;}FOR(i, 1, N+1){fib[i] += fib[i-1];fib[i] %= mod;}}int main(void){cin.tie(0);ios::sync_with_stdio(false);scanf("%d %d", &N, &Q);init();vector<value> v(N);REP(i, N){v[i] = value(0, i, i+1);}LazySegTree<vmonoid, omonoid, modifier>lsg(v.begin(), v.end());REP(i, Q){int64 q, l, r, k;scanf("%lld %lld %lld %lld", &q, &l, &r, &k); r++;if(q == 0){printf("%lld\n", lsg.query(l, r).v*k%mod);}else if(q == 1){lsg.update(l, r, omonoid::value_type(0, 1, k, 0));}else if(q == 2){lsg.update(l, r, omonoid::value_type(k, 1, -1, 0));}else if(q == 3){lsg.update(l, r, omonoid::value_type(0, k, -1, 0));}else if(q == 4){lsg.update(l, r, omonoid::value_type(0, 1, -1, k));}/*REP(i, N){cout << lsg[i].v << " ";}cout << endl;*/}}