Submit Info #59390

Problem Lang User Status Time Memory
Range Affine Range Sum cpp Soapen AC 584 ms 14.74 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.45 MiB
max_random_00 AC 582 ms 14.74 MiB
max_random_01 AC 584 ms 14.70 MiB
max_random_02 AC 584 ms 14.74 MiB
random_00 AC 477 ms 14.37 MiB
random_01 AC 486 ms 14.37 MiB
random_02 AC 283 ms 3.71 MiB
small_00 AC 1 ms 0.45 MiB
small_01 AC 1 ms 0.45 MiB
small_02 AC 1 ms 0.45 MiB
small_03 AC 1 ms 0.45 MiB
small_04 AC 1 ms 0.45 MiB
small_05 AC 1 ms 0.45 MiB
small_06 AC 1 ms 0.47 MiB
small_07 AC 1 ms 0.45 MiB
small_08 AC 1 ms 0.42 MiB
small_09 AC 1 ms 0.45 MiB
small_random_00 AC 1 ms 0.42 MiB
small_random_01 AC 1 ms 0.45 MiB

// freopen("../../p257.t13.in", "r", stdin); #include <bits/stdc++.h> #define rep(a, b) for(int a = 0; a < (b); ++a) #define all(a) (a).begin(),(a).end() #define endl '\n' using namespace std; using Graph = vector<vector<int>>; using ll = long long; namespace cpc { int floor_log2(int n) { return n ? 31 - __builtin_clz(n) : 0; } int ceil_log2(int n) { return floor_log2(n) + (__builtin_popcount(n)!=1); } template<class Conf> struct SegTreeImpl { using T = typename Conf::T; // data type using U = typename Conf::U; // update type int width(int v) { return (int)n >> floor_log2(v); } int left(int v) { return width(v) * (v ^ (1 << floor_log2(v))); } int right(int v) { return left(v) + width(v); } int n; vector<T> d; // node values vector<U> lazy; // exclusive lazy SegTreeImpl(int _n) : n(1 << ceil_log2(_n)), d(2*n, Conf::NEUTRAL) { if constexpr(Conf::LAZY) lazy.resize(2*n, Conf::UNCHANGED); } void update(int i, T val) { flush(n+i); d[n+i]= val; rebuild(n+i); } void update(int l, int r, const U& upd) { flush(n + l); flush(n + r - 1); for (int li=n+l, ri =n+r; li<ri; li/=2, ri/=2) { if (li % 2) Conf::apply(*this, li++, upd); if (ri % 2) Conf::apply(*this, --ri, upd); } rebuild(trunc(n+l)); // rebuild above first changed nodes rebuild(trunc(n+r)-1); } T& query(int i) { flush(n + i); return d[n+i]; } T query(int l, int r) { flush(n + l); flush(n + r - 1); T rl = Conf::NEUTRAL, rr = Conf::NEUTRAL; for(l+=n, r+=n; l<r; l/=2, r/=2) { if(l&1) rl = Conf::combine(rl, d[l++]); if(r&1) rr = Conf::combine(d[--r], rr); } return Conf::combine(rl, rr); } template <class Pred> int lower_bound(Pred pred) { if (!pred(d[1])) return n; T pref = Conf::NEUTRAL; int i = 1; while (i<n) { push(i); if(!pred(Conf::combine(pref, d[i*=2]))) pref = Conf::combine(pref, d[i++]); } return i - n; } private: // push lazy down one layer void push(int v) { if constexpr(Conf::LAZY) { if(lazy[v]==Conf::UNCHANGED) return; Conf::apply(*this, 2*v, lazy[v]); Conf::apply(*this, 2*v+1, lazy[v]); lazy[v] = Conf::UNCHANGED; } } // push lazy updates of all parents down to v void flush(int v) { if constexpr(Conf::LAZY) { for(int b = floor_log2(v); b; --b) push(v>>b); }; } // rebuild v and all its parents void rebuild(int v) { while(v/=2) d[v] = Conf::combine(d[2*v], d[2*v+1]); } // shifts all trailing zeros away; (= first parent of v that is touched in query) int trunc(int v) { return v >> __builtin_ctz(v); } }; } const int MOD = 998244353; auto composite(pair<int,int> a, pair<int,int> b) { // returns function b(a(x)) return pair{ll(a.first)*b.first%MOD, (ll(b.first)*a.second + b.second)%MOD}; } struct SegTreeConf { using T = int; static constexpr T NEUTRAL = 0; static T combine(const T& a, const T& b) { return (a+b)%MOD; } // lazy part const static bool LAZY = true; using U = pair<int,int>; static constexpr U UNCHANGED = {1,0}; void static apply(cpc::SegTreeImpl<SegTreeConf>& seg, int v, const U& upd) { seg.d[v] = (ll(upd.first)*seg.d[v] + ll(upd.second)*seg.width(v)) % MOD; if(v<seg.n) seg.lazy[v] = composite(seg.lazy[v], upd); } }; using SegTree = cpc::SegTreeImpl<SegTreeConf>; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.precision(10); int n,q; cin>>n>>q; SegTree seg(n); rep(i,n) { int a; cin>>a; seg.update(i,a); } rep(i,q) { int t; cin>>t; if(t==0) { int l,r,a,b; cin>>l>>r>>a>>b; seg.update(l,r, {a,b}); } else { int l,r; cin>>l>>r; cout << seg.query(l,r) << endl; } } return 0; }