This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub
#define PROBLEM "https://judge.yosupo.jp/problem/range_affine_range_sum" #include "C++/math/Modint.hpp" #include "C++/ds/LazySegmentTree.hpp" using Z = zwei<mint>; int main() { int n, q; std::cin >> n >> q; LazySegTree<Z, Z> seg(n, [](const Z &a, const Z &b) -> Z { return Z(a.first + b.first, a.second + b.second); }, [](const Z &a, const Z &b) -> Z { return Z(a.first * b.first + a.second * b.second, a.second); }, [](const Z &a, const Z &b) -> Z { return Z(a.first * b.first, a.second * b.first + b.second); }, Z(0, 0), Z(1, 0)); std::vector<Z> a(n); for(int i = 0; i < n; ++i) { int x; std::cin >> x; a[i] = Z(x, 1); } seg.build(a); while(q--) { int t, l, r; std::cin >> t >> l >> r; if(t == 0) { int p, q; std::cin >> p >> q; seg.apply(l, r, Z(p, q)); } else { std::cout << seg.query(l, r) << '\n'; } } } // verified but actually failed(slowest: 9.000372 sec.)
#line 1 "test/rangeaffine.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/range_affine_range_sum" #line 2 "C++/math/Modint.hpp" #pragma GCC diagnostic ignored "-Wdeprecated-copy" #include <iostream> #include <cassert> #include <vector> #include <utility> #include <type_traits> #include <numeric> #ifndef TEMPLATE typedef long long ll; typedef unsigned uint; typedef unsigned long long ul; #endif template <uint mod> struct Modint { uint num = 0; constexpr Modint() noexcept {} constexpr Modint(const Modint &x) noexcept : num(x.num){} constexpr operator ll() const noexcept { return num; } constexpr static uint get_mod(){ return mod; } constexpr Modint& operator+=(Modint x) noexcept { num += x.num; if(num >= mod) num -= mod; return *this; } constexpr Modint& operator++() noexcept { if(num == mod - 1) num = 0; else num++; return *this; } constexpr Modint operator++(int) noexcept { Modint ans(*this); operator++(); return ans; } constexpr Modint operator-() const noexcept { return Modint(0) -= *this; } constexpr Modint& operator-=(Modint x) noexcept { if(num < x.num) num += mod; num -= x.num; return *this; } constexpr Modint& operator--() noexcept { if(num == 0) num = mod - 1; else num--; return *this; } constexpr Modint operator--(int) noexcept { Modint ans(*this); operator--(); return ans; } constexpr Modint& operator*=(Modint x) noexcept { num = ul(num) * x.num % mod; return *this; } constexpr Modint& operator/=(Modint x) noexcept { return operator*=(x.inv()); } constexpr void operator%=(Modint x) noexcept { void(0); } template <class T> constexpr Modint(T x) noexcept { using U = typename std::conditional<sizeof(T)>= 4, T, int>::type; U y = x; y %= U(mod); if(y < 0) y += mod; num = uint(y); } template <class T> constexpr Modint operator+(T x) const noexcept { return Modint(*this) += x; } template <class T> constexpr Modint& operator+=(T x) noexcept { return operator+=(Modint(x)); } template <class T> constexpr Modint operator-(T x) const noexcept { return Modint(*this) -= x; } template <class T> constexpr Modint& operator-=(T x) noexcept { return operator-=(Modint(x)); } template <class T> constexpr Modint operator*(T x) const noexcept { return Modint(*this) *= x; } template <class T> constexpr Modint& operator*=(T x) noexcept { return operator*=(Modint(x)); } template <class T> constexpr Modint operator/(T x) const noexcept { return Modint(*this) /= x; } template <class T> constexpr Modint& operator/=(T x) noexcept { return operator/=(Modint(x)); } constexpr Modint inv() const noexcept { ll x = 0, y = 0; extgcd(num, mod, x, y); return x; } static constexpr ll extgcd(ll a, ll b, ll &x, ll &y) noexcept { ll g = a; x = 1; y = 0; if(b){ g = extgcd(b, a % b, y, x); y -= a / b * x; } return g; } constexpr Modint pow(ul x) const noexcept { Modint ans = 1, cnt = *this; while(x){ if(x & 1) ans *= cnt; cnt *= cnt; x /= 2; } return ans; } friend std::ostream& operator<<(std::ostream& os, const Modint& m){ os << m.num; return os; } friend std::istream &operator>>(std::istream &is, Modint &a) { ll t; is >> t; a=Modint(t); return (is); } }; using mint = Modint<998244353>; using Mint = Modint<1000000007>; template <class T> inline T msum(const std::vector<T> &v){ return std::accumulate(v.begin(), v.end(), mint(0)); } template <class T> inline T msum(const std::vector<T> &v, ll a, ll b){ return std::accumulate(v.begin() + a, v.begin() + b, mint(0)); } template <class T> inline T mmul(const std::vector<T> &v){ return std::accumulate(v.begin(), v.end(), mint(1), [](T acc, T i){ return acc*i; }); } template <class T> inline T mmul(const std::vector<T> &v, ll a, ll b){ return std::accumulate(v.begin() + a, v.begin() + b, mint(1), [](T acc, T i){ return acc*i; }); } template <class mint> struct Comb { private: std::vector<mint> fac{1},inv{1}; void reserve(ul a){ if(fac.size()>=a) return; if(a<fac.size()*2) a=fac.size()*2; if(a>=mint::get_mod()) a=mint::get_mod(); while(fac.size()<a) fac.emplace_back(fac.back()*mint(fac.size())); inv.resize(fac.size()); inv.back()=fac.back().inv(); for(ll i=inv.size()-1; !inv[i-1]; i--) inv[i-1]=inv[i]*i; } public: mint fact(const ll n){ if(n<0) return 0; reserve(n + 1); return fac[n]; } mint nPr(ll n, const ll r){ if(r<0 || n<r) return 0; if(n>>24){ mint ans=1; for(int i = 0; i < r; ++i) ans*=n--; return ans; } reserve(n+1); return fac[n]*inv[n-r]; } mint nCr(const ll n, ll r){ if(r<0 || n<r) return 0; r=std::min(r,n-r); reserve(r+1); return nPr(n,r)*inv[r]; } mint nHr(const ll n, const ll r){ if(!n && !r) return 1; if(n<=0 || r<0) return 0; return nCr(n+r-1,r); } }; struct a_mint { int val; a_mint() : val(0){} a_mint(ll x) : val(x >= 0 ? x % get_mod() : (get_mod() - (-x) % get_mod()) % get_mod()){} int getmod() { return get_mod(); } static int &get_mod() { static int mod = 0; return mod; } static void set_mod(int md) { assert(md>0); get_mod() = md; } a_mint &operator+=(const a_mint &p) { if ((val += p.val) >= get_mod()) val -= get_mod(); return *this; } a_mint &operator-=(const a_mint &p) { if((val += get_mod() - p.val) >= get_mod()) val -= get_mod(); return *this; } a_mint &operator*=(const a_mint &p) { val = (int)(1LL * val * p.val % get_mod()); return *this; } a_mint &operator/=(const a_mint &p) { *this *= p.inv(); return *this; } a_mint operator-() const { return a_mint(-val); } a_mint operator+(const a_mint &p) const { return a_mint(*this) += p; } a_mint operator-(const a_mint &p) const { return a_mint(*this) -= p; } a_mint operator*(const a_mint &p) const { return a_mint(*this) *= p; } a_mint operator/(const a_mint &p) const { return a_mint(*this) /= p; } a_mint& operator++() noexcept { if(val == get_mod() - 1) val = 0; else val++; return *this; } a_mint operator++(int) noexcept { a_mint ans(*this); operator++(); return ans; } a_mint& operator--() noexcept { if(val == 0) val = get_mod() - 1; else val--; return *this; } a_mint operator--(int) noexcept { a_mint ans(*this); operator--(); return ans; } bool operator==(const a_mint &p) const { return val == p.val; } bool operator!=(const a_mint &p) const { return val != p.val; } bool operator!() const { return val == 0; } bool operator<=(const a_mint &p) const { return val <= p.val; } bool operator>=(const a_mint &p) const { return val >= p.val; } bool operator<(const a_mint &p) const { return val < p.val; } bool operator>(const a_mint &p) const { return val > p.val; } a_mint inv() const { int a=val, b=get_mod(), u=1, v=0, t; while(b>0) { t=a/b; std::swap(a -= t*b,b); std::swap(u -= t*v,v); } return a_mint(u); } a_mint pow(ll n) const { a_mint res(1), mul(val); while(n>0) { if(n & 1) res *= mul; mul *= mul; n >>= 1; } return res; } friend std::ostream &operator<<(std::ostream &os, const a_mint &p) { return os << p.val; } friend std::istream &operator>>(std::istream &is, a_mint &a) { ll t; is >> t; a=a_mint(t); return is; } }; /** * @brief Modint * @docs docs/Modint.md * @see https://atcoder.jp/contests/arc151/submissions/35526971 */ #line 2 "C++/ds/LazySegmentTree.hpp" #include <ostream> #line 6 "C++/ds/LazySegmentTree.hpp" #include <functional> template <class T, class U> struct LazySegTree { private: using F = std::function<T(T, T)>; using M = std::function<T(T, U)>; using C = std::function<U(U, U)>; int n, sz, h; std::vector<T> data; std::vector<U> lazy; const F f; const M map; const C comp; const T e; const U id; inline void update(const int k){ data[k] = f(data[2 * k], data[2 * k + 1]); } inline void all_apply(const int k, const U &x) { data[k] = map(data[k], x); if(k < sz) { lazy[k] = comp(lazy[k], x); } } inline void propagate(const int k) { if(lazy[k] != id) { all_apply(2 * k, lazy[k]); all_apply(2 * k + 1, lazy[k]); lazy[k] = id; } } public: LazySegTree(const int n, const F &f, const M &map, const C &comp, const T &e, const U &id): n(n), f(f), map(map), comp(comp), e(e), id(id) { sz = 1; h = 0; while(sz < n) { sz <<= 1; h++; } data.assign(2 * sz, e); lazy.assign(2 * sz, id); } LazySegTree(const std::vector<T> &v, const F &f, const M &map, const C &comp, const T &e, const U &id): LazySegTree(v.size(), f, map, comp, e, id){ build(v); } void build(const std::vector<T> &v) { assert(n == (int) v.size()); for(int k = 0; k < n; ++k) { data[k + sz] = v[k]; } for(int k = sz; --k > 0;) { update(k); } } void set(int k, const T &x) { k += sz; for(int i = h; i > 0; i--) { propagate(k >> i); } data[k] = x; for(int i = 0; ++i <= h;) { update(k >> i); } } T &operator[](int k) { k += sz; for(int i = h; i > 0; i--) { propagate(k >> i); } return data[k]; } T const& operator[](const int k) const { return data[k + sz]; } T query(int l, int r) { if(l >= r) { return e; } l += sz; r += sz; for(int i = h; i > 0; i--) { if(((l >> i) << i) != l) { propagate(l >> i); } if(((r >> i) << i) != r) { propagate((r - 1) >> i); } } T L = e, R = e; for(; l < r; l >>= 1, r >>= 1) { if(l & 1) { L = f(L, data[l++]); } if(r & 1) { R = f(data[--r], R); } } return f(L, R); } T alle() const { return data[1]; } void apply(int k, const U &x) { k += sz; for(int i = h; i > 0; i--) { propagate(k >> i); } data[k] = map(data[k], x); for(int i = 0; ++i <= h;) { update(k >> i); } } void apply(int l, int r, const U &x) { if(l >= r) { return; } l += sz; r += sz; for(int i = h; i > 0; i--) { if(((l >> i) << i) != l) { propagate(l >> i); } if(((r >> i) << i) != r) { propagate((r - 1) >> i); } } int l2 = l, r2 = r; for(; l < r; l >>= 1, r >>= 1) { if(l & 1) { all_apply(l++, x); } if(r & 1) { all_apply(--r, x); } } l = l2, r = r2; for(int i = 0; ++i <= h;) { if(((l >> i) << i) != l) { update(l >> i); } if(((r >> i) << i) != r) { update((r - 1) >> i); } } } inline int size() const { return n; } template <class Boolean> int find_first(int l, const Boolean &fn) { if(l >= n) { return n; } l += sz; for(int i = h; i > 0; i--) { propagate(l >> i); } T sum = e; do { while((l & 1) == 0) { l >>= 1; } if(fn(f(sum, data[l]))) { while(l < sz) { propagate(l); l <<= 1; const auto nxt = f(sum, data[l]); if(!fn(nxt)) { sum = nxt; l++; } } return l + 1 - sz; } sum = f(sum, data[l++]); } while((l & -l) != l); return n; } template <class Boolean> int find_last(int r, const Boolean &fn) { if(r <= 0) { return -1; } r += sz; for(int i = h; i > 0; i--) { propagate((r - 1) >> i); } T sum = e; do { r--; while(r > 1 && r & 1) { r >>= 1; } if(fn(f(data[r], sum))) { while(r < sz) { propagate(r); r = (r << 1) + 1; const auto nxt = f(data[r], sum); if(!fn(nxt)) { sum = nxt; r--; } } return r - sz; } sum = f(data[r], sum); } while((r & -r) != r); return -1; } void clear(){ std::fill(data.cbegin(), data.cend(), e); } friend std::ostream &operator<<(std::ostream &os, const LazySegTree &seg) { os << seg[0]; for(int i = 0; ++i < seg.size();) { os << ' ' << seg[i]; } return os; } }; #include <cmath> #include <limits> template <class T> struct zwei { T first, second; zwei(){} zwei(const T &f, const T &s): first(f), second(s){} constexpr bool operator!=(const zwei<T> &z) noexcept { return first != z.first || second != z.second; } operator T() const { return first; } friend std::ostream &operator<<(std::ostream &os, const zwei &z) { os << z.first; return os; } }; template <class T> struct RAMX: LazySegTree<T, T> { RAMX(const std::vector<T> &v): LazySegTree<T, T>(v, [](const T a, const T b){ return std::max(a, b); }, [](const T a, const T b){ return a + b; }, [](const T a, const T b){ return a + b; }, std::numeric_limits<T>::min(), 0){} }; template <class T> struct RAMN: LazySegTree<T, T> { RAMN(const std::vector<T> &v): LazySegTree<T, T>(v, [](const T a, const T b){ return std::min(a, b); }, [](const T a, const T b){ return a + b; }, [](const T a, const T b){ return a + b; }, std::numeric_limits<T>::max(), 0){} }; template <class T> struct RASM: LazySegTree<zwei<T>, T> { RASM(const std::vector<T> &v): LazySegTree<zwei<T>, T>(v.size(), [](const zwei<T> a, const zwei<T> b){ return zwei<T>(a.first + b.first, a.second + b.second); }, [](const zwei<T> a, const T b){ return zwei<T>(a.first + a.second * b, a.second); }, [](const T a, const T b){ return a + b; }, zwei<T>(0, 0), 0) { std::vector<zwei<T>> w(v.size()); for(size_t i = 0; i < v.size(); ++i) { w[i] = zwei<T>(v[i], 1); } LazySegTree<zwei<T>, T>::build(w); } }; template <class T> struct RUMX: LazySegTree<T, T> { RUMX(const std::vector<T> &v): LazySegTree<T, T>(v, [](const T a, const T b){ return std::max(a, b); }, [](const T, const T b){ return b; }, [](const T, const T b){ return b; }, std::numeric_limits<T>::min(), std::numeric_limits<T>::min()){} }; template <class T> struct RUMN: LazySegTree<T, T> { RUMN(const std::vector<T> &v): LazySegTree<T, T>(v, [](const T a, const T b){ return std::min(a, b); }, [](const T, const T b){ return b; }, [](const T, const T b){ return b; }, std::numeric_limits<T>::max(), std::numeric_limits<T>::max()){} }; template <class T> struct RUSM: LazySegTree<zwei<T>, T> { RUSM(const std::vector<T> &v): LazySegTree<zwei<T>, T>(v.size(), [](const zwei<T> a, const zwei<T> b){ return zwei<T>(a.first + b.first, a.second + b.second); }, [](const zwei<T> a, const T b){ return zwei<T>(a.second * b, a.second); }, [](const T a, const T b){ return b; }, zwei<T>(0, 0), std::numeric_limits<T>::min()) { std::vector<zwei<T>> w(v.size()); for(size_t i = 0; i < v.size(); ++i) { w[i] = zwei<T>(v[i], 1); } LazySegTree<zwei<T>, T>::build(w); } }; /** * @brief 遅延セグ木 * @see https://ei1333.github.io/library/structure/segment-tree/lazy-segment-tree.hpp */ #line 4 "test/rangeaffine.test.cpp" using Z = zwei<mint>; int main() { int n, q; std::cin >> n >> q; LazySegTree<Z, Z> seg(n, [](const Z &a, const Z &b) -> Z { return Z(a.first + b.first, a.second + b.second); }, [](const Z &a, const Z &b) -> Z { return Z(a.first * b.first + a.second * b.second, a.second); }, [](const Z &a, const Z &b) -> Z { return Z(a.first * b.first, a.second * b.first + b.second); }, Z(0, 0), Z(1, 0)); std::vector<Z> a(n); for(int i = 0; i < n; ++i) { int x; std::cin >> x; a[i] = Z(x, 1); } seg.build(a); while(q--) { int t, l, r; std::cin >> t >> l >> r; if(t == 0) { int p, q; std::cin >> p >> q; seg.apply(l, r, Z(p, q)); } else { std::cout << seg.query(l, r) << '\n'; } } } // verified but actually failed(slowest: 9.000372 sec.)