This documentation is automatically generated by competitive-verifier/competitive-verifier
// @brief Range Affine Range Sum
#define PROBLEM "https://judge.yosupo.jp/problem/range_affine_range_sum"
#include "cp-algo/data_structures/segtree/metas/affine.hpp"
#include "cp-algo/data_structures/segtree.hpp"
#include "cp-algo/number_theory/modint.hpp"
#include <bits/stdc++.h>
using namespace std;
using namespace cp_algo::data_structures;
using base = cp_algo::math::modint<998244353>;
using meta = segtree::metas::affine_meta<base>;
void solve() {
int n, q;
cin >> n >> q;
vector<meta> a(n);
for(int i = 0; i < n; i++) {
int ai;
cin >> ai;
a[i] = {ai};
}
segtree_t<meta> me(a);
while(q--) {
int t;
cin >> t;
if(t == 0) {
int l, r, b, c;
cin >> l >> r >> b >> c;
me.exec_on_segment(l, r, [&](auto& meta) {
meta.to_push.prepend(meta::lin(b, c));
});
} else {
int l, r;
cin >> l >> r;
base ans = 0;
me.exec_on_segment(l, r, [&](auto meta) {
ans += meta.sum;
});
cout << ans << "\n";
}
}
}
signed main() {
//freopen("input.txt", "r", stdin);
ios::sync_with_stdio(0);
cin.tie(0);
int t = 1;
while(t--) {
solve();
}
}
#line 1 "verify/data_structures/segtree/range_affine_range_sum.test.cpp"
// @brief Range Affine Range Sum
#define PROBLEM "https://judge.yosupo.jp/problem/range_affine_range_sum"
#line 1 "cp-algo/data_structures/segtree/metas/affine.hpp"
#line 1 "cp-algo/data_structures/segtree/metas/base.hpp"
namespace cp_algo::data_structures::segtree::metas {
template<typename derived_meta>
struct base_meta {
using meta = derived_meta;
virtual void pull(meta const&, meta const&, int, int) {};
virtual void push(meta*, meta*, int, int) {};
};
}
#line 1 "cp-algo/math/affine.hpp"
#include <optional>
#include <utility>
#include <cassert>
#include <tuple>
namespace cp_algo::math {
// a * x + b
template<typename base>
struct lin {
base a = 1, b = 0;
std::optional<base> c;
lin() {}
lin(base b): a(0), b(b) {}
lin(base a, base b): a(a), b(b) {}
lin(base a, base b, base _c): a(a), b(b), c(_c) {}
// polynomial product modulo x^2 - c
lin operator * (const lin& t) {
assert(c && t.c && *c == *t.c);
return {a * t.b + b * t.a, b * t.b + a * t.a * (*c), *c};
}
// a * (t.a * x + t.b) + b
lin apply(lin const& t) const {
return {a * t.a, a * t.b + b};
}
void prepend(lin const& t) {
*this = t.apply(*this);
}
base eval(base x) const {
return a * x + b;
}
};
// (ax+b) / (cx+d)
template<typename base>
struct linfrac {
base a, b, c, d;
linfrac(): a(1), b(0), c(0), d(1) {} // x, identity for composition
linfrac(base a): a(a), b(1), c(1), d(0) {} // a + 1/x, for continued fractions
linfrac(base a, base b, base c, base d): a(a), b(b), c(c), d(d) {}
// composition of two linfracs
linfrac operator * (linfrac t) const {
return t.prepend(linfrac(*this));
}
linfrac operator-() const {
return {-a, -b, -c, -d};
}
linfrac adj() const {
return {d, -b, -c, a};
}
linfrac& prepend(linfrac const& t) {
t.apply(a, c);
t.apply(b, d);
return *this;
}
// apply linfrac to A/B
void apply(base &A, base &B) const {
std::tie(A, B) = std::pair{a * A + b * B, c * A + d * B};
}
};
}
#line 5 "cp-algo/data_structures/segtree/metas/affine.hpp"
namespace cp_algo::data_structures::segtree::metas {
template<typename base>
struct affine_meta: base_meta<affine_meta<base>> {
using meta = affine_meta;
using lin = math::lin<base>;
base sum = 0;
lin to_push = {};
affine_meta() {}
affine_meta(base sum): sum(sum) {}
void push(meta *L, meta *R, int l, int r) override {
if(to_push.a != 1 || to_push.b != 0) {
sum = to_push.a * sum + to_push.b * (r - l);
if(r - l > 1) {
L->to_push.prepend(to_push);
R->to_push.prepend(to_push);
}
to_push = {};
}
}
void pull(meta const& L, meta const& R, int, int) override {
sum = L.sum + R.sum;
}
};
}
#line 1 "cp-algo/data_structures/segtree.hpp"
#include <vector>
namespace cp_algo::data_structures {
template<typename meta>
struct segtree_t {
const int N;
std::vector<meta> _meta;
segtree_t(int n): N(n), _meta(4 * N) {}
segtree_t(std::vector<meta> leafs): N(size(leafs)), _meta(4 * N) {
build(leafs);
}
void pull(int v, int l, int r) {
if(r - l > 1) {
_meta[v].pull(_meta[2 * v], _meta[2 * v + 1], l, r);
}
}
void push(int v, int l, int r) {
if(r - l > 1) {
_meta[v].push(&_meta[2 * v], &_meta[2 * v + 1], l, r);
} else {
_meta[v].push(nullptr, nullptr, l, r);
}
}
void build(auto &a, int v, size_t l, size_t r) {
if(r - l == 1) {
if(l < size(a)) {
_meta[v] = a[l];
}
} else {
size_t m = (l + r) / 2;
build(a, 2 * v, l, m);
build(a, 2 * v + 1, m, r);
pull(v, l, r);
}
}
void build(auto &a) {
build(a, 1, 0, N);
}
void exec_on_segment(int a, int b, auto func, auto proceed, auto stop, int v, int l, int r) {
push(v, l, r);
if(r <= a || b <= l || stop(_meta[v])) {
return;
} else if(a <= l && r <= b && proceed(_meta[v])) {
func(_meta[v]);
push(v, l, r);
} else {
int m = (l + r) / 2;
exec_on_segment(a, b, func, proceed, stop, 2 * v, l, m);
exec_on_segment(a, b, func, proceed, stop, 2 * v + 1, m, r);
pull(v, l, r);
}
}
static constexpr auto default_true = [](auto const&){return true;};
static constexpr auto default_false = [](auto const&){return false;};
void exec_on_segment(int a, int b, auto func, auto proceed, auto stop) {
exec_on_segment(a, b, func, proceed, stop, 1, 0, N);
}
void exec_on_segment(int a, int b, auto func) {
exec_on_segment(a, b, func, default_true, default_false);
}
};
}
#line 1 "cp-algo/number_theory/modint.hpp"
#line 1 "cp-algo/math/common.hpp"
#include <functional>
#include <cstdint>
namespace cp_algo::math {
#ifdef CP_ALGO_MAXN
const int maxn = CP_ALGO_MAXN;
#else
const int maxn = 1 << 19;
#endif
const int magic = 64; // threshold for sizes to run the naive algo
auto bpow(auto const& x, int64_t n, auto const& one, auto op) {
if(n == 0) {
return one;
} else {
auto t = bpow(x, n / 2, one, op);
t = op(t, t);
if(n % 2) {
t = op(t, x);
}
return t;
}
}
auto bpow(auto x, int64_t n, auto ans) {
return bpow(x, n, ans, std::multiplies{});
}
template<typename T>
T bpow(T const& x, int64_t n) {
return bpow(x, n, T(1));
}
}
#line 4 "cp-algo/number_theory/modint.hpp"
#include <iostream>
#line 6 "cp-algo/number_theory/modint.hpp"
namespace cp_algo::math {
inline constexpr uint64_t inv64(uint64_t x) {
assert(x % 2);
uint64_t y = 1;
while(y * x != 1) {
y *= 2 - x * y;
}
return y;
}
template<typename modint>
struct modint_base {
static int64_t mod() {
return modint::mod();
}
static uint64_t imod() {
return modint::imod();
}
static __uint128_t pw128() {
return modint::pw128();
}
static uint64_t m_reduce(__uint128_t ab) {
if(mod() % 2 == 0) [[unlikely]] {
return ab % mod();
} else {
uint64_t m = ab * imod();
return (ab + __uint128_t(m) * mod()) >> 64;
}
}
static uint64_t m_transform(uint64_t a) {
if(mod() % 2 == 0) [[unlikely]] {
return a;
} else {
return m_reduce(a * pw128());
}
}
modint_base(): r(0) {}
modint_base(int64_t rr): r(rr % mod()) {
r = std::min(r, r + mod());
r = m_transform(r);
}
modint inv() const {
return bpow(to_modint(), mod() - 2);
}
modint operator - () const {
modint neg;
neg.r = std::min(-r, 2 * mod() - r);
return neg;
}
modint& operator /= (const modint &t) {
return to_modint() *= t.inv();
}
modint& operator *= (const modint &t) {
r = m_reduce(__uint128_t(r) * t.r);
return to_modint();
}
modint& operator += (const modint &t) {
r += t.r; r = std::min(r, r - 2 * mod());
return to_modint();
}
modint& operator -= (const modint &t) {
r -= t.r; r = std::min(r, r + 2 * mod());
return to_modint();
}
modint operator + (const modint &t) const {return modint(to_modint()) += t;}
modint operator - (const modint &t) const {return modint(to_modint()) -= t;}
modint operator * (const modint &t) const {return modint(to_modint()) *= t;}
modint operator / (const modint &t) const {return modint(to_modint()) /= t;}
// Why <=> doesn't work?..
auto operator == (const modint_base &t) const {return getr() == t.getr();}
auto operator != (const modint_base &t) const {return getr() != t.getr();}
auto operator <= (const modint_base &t) const {return getr() <= t.getr();}
auto operator >= (const modint_base &t) const {return getr() >= t.getr();}
auto operator < (const modint_base &t) const {return getr() < t.getr();}
auto operator > (const modint_base &t) const {return getr() > t.getr();}
int64_t rem() const {
uint64_t R = getr();
return 2 * R > (uint64_t)mod() ? R - mod() : R;
}
// Only use if you really know what you're doing!
uint64_t modmod() const {return 8ULL * mod() * mod();};
void add_unsafe(uint64_t t) {r += t;}
void pseudonormalize() {r = std::min(r, r - modmod());}
modint const& normalize() {
if(r >= (uint64_t)mod()) {
r %= mod();
}
return to_modint();
}
void setr(uint64_t rr) {r = m_transform(rr);}
uint64_t getr() const {
uint64_t res = m_reduce(r);
return std::min(res, res - mod());
}
void setr_direct(uint64_t rr) {r = rr;}
uint64_t getr_direct() const {return std::min(r, r - mod());}
private:
uint64_t r;
modint& to_modint() {return static_cast<modint&>(*this);}
modint const& to_modint() const {return static_cast<modint const&>(*this);}
};
template<typename modint>
std::istream& operator >> (std::istream &in, modint_base<modint> &x) {
uint64_t r;
auto &res = in >> r;
x.setr(r);
return res;
}
template<typename modint>
std::ostream& operator << (std::ostream &out, modint_base<modint> const& x) {
return out << x.getr();
}
template<typename modint>
concept modint_type = std::is_base_of_v<modint_base<modint>, modint>;
template<int64_t m>
struct modint: modint_base<modint<m>> {
static constexpr uint64_t im = m % 2 ? inv64(-m) : 0;
static constexpr uint64_t r2 = __uint128_t(-1) % m + 1;
static constexpr int64_t mod() {return m;}
static constexpr uint64_t imod() {return im;}
static constexpr __uint128_t pw128() {return r2;}
using Base = modint_base<modint<m>>;
using Base::Base;
};
struct dynamic_modint: modint_base<dynamic_modint> {
static int64_t mod() {return m;}
static uint64_t imod() {return im;}
static __uint128_t pw128() {return r2;}
static void switch_mod(int64_t nm) {
m = nm;
im = m % 2 ? inv64(-m) : 0;
r2 = __uint128_t(-1) % m + 1;
}
using Base = modint_base<dynamic_modint>;
using Base::Base;
// Wrapper for temp switching
auto static with_mod(int64_t tmp, auto callback) {
struct scoped {
int64_t prev = mod();
~scoped() {switch_mod(prev);}
} _;
switch_mod(tmp);
return callback();
}
private:
static int64_t m;
static uint64_t im, r1, r2;
};
int64_t dynamic_modint::m = 1;
uint64_t dynamic_modint::im = -1;
uint64_t dynamic_modint::r2 = 0;
}
#line 6 "verify/data_structures/segtree/range_affine_range_sum.test.cpp"
#include <bits/stdc++.h>
using namespace std;
using namespace cp_algo::data_structures;
using base = cp_algo::math::modint<998244353>;
using meta = segtree::metas::affine_meta<base>;
void solve() {
int n, q;
cin >> n >> q;
vector<meta> a(n);
for(int i = 0; i < n; i++) {
int ai;
cin >> ai;
a[i] = {ai};
}
segtree_t<meta> me(a);
while(q--) {
int t;
cin >> t;
if(t == 0) {
int l, r, b, c;
cin >> l >> r >> b >> c;
me.exec_on_segment(l, r, [&](auto& meta) {
meta.to_push.prepend(meta::lin(b, c));
});
} else {
int l, r;
cin >> l >> r;
base ans = 0;
me.exec_on_segment(l, r, [&](auto meta) {
ans += meta.sum;
});
cout << ans << "\n";
}
}
}
signed main() {
//freopen("input.txt", "r", stdin);
ios::sync_with_stdio(0);
cin.tie(0);
int t = 1;
while(t--) {
solve();
}
}
Env | Name | Status | Elapsed | Memory |
---|---|---|---|---|
g++ | example_00 | AC | 5 ms | 3 MB |
g++ | max_random_00 | AC | 1052 ms | 144 MB |
g++ | max_random_01 | AC | 1027 ms | 144 MB |
g++ | max_random_02 | AC | 1051 ms | 144 MB |
g++ | random_00 | AC | 851 ms | 113 MB |
g++ | random_01 | AC | 856 ms | 133 MB |
g++ | random_02 | AC | 537 ms | 18 MB |
g++ | small_00 | AC | 5 ms | 4 MB |
g++ | small_01 | AC | 5 ms | 4 MB |
g++ | small_02 | AC | 5 ms | 4 MB |
g++ | small_03 | AC | 5 ms | 4 MB |
g++ | small_04 | AC | 6 ms | 4 MB |
g++ | small_05 | AC | 5 ms | 4 MB |
g++ | small_06 | AC | 6 ms | 4 MB |
g++ | small_07 | AC | 5 ms | 4 MB |
g++ | small_08 | AC | 5 ms | 4 MB |
g++ | small_09 | AC | 5 ms | 4 MB |
g++ | small_random_00 | AC | 6 ms | 4 MB |
g++ | small_random_01 | AC | 5 ms | 4 MB |