VvyLw's Library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub

:heavy_check_mark: test/rangeaffine.test.cpp

Depends on

Code

#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.)
Back to top page