test/yosupo/range_affine_point_get.DynSeg.test.cpp

• View this file on GitHub
• Last update: 2024-10-12 14:37:37+09:00
• Problem: https://judge.yosupo.jp/problem/range_affine_point_get

Depends on

• Segment-Tree(動的構築) (src/DataStructure/SegmentTree_Dynamic.hpp)
• メンバの有無を判定するテンプレート 他 (src/Internal/HAS_CHECK.hpp)
• modintを扱うテンプレート (src/Internal/modint_traits.hpp)
• 剰余の高速化 (src/Internal/Remainder.hpp)
• 逆元 ($\mathbb{Z}/m\mathbb{Z}$) (src/Math/mod_inv.hpp)
• ModInt (src/Math/ModInt.hpp)

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/range_affine_point_get
// competitive-verifier: TLE 1
// competitive-verifier: MLE 64
// 双対 の verify

#include <iostream>
#include <array>
#include "src/Math/ModInt.hpp"
#include "src/DataStructure/SegmentTree_Dynamic.hpp"
using namespace std;
using Mint= ModInt<998244353>;
struct M {
 using T= Mint;
 using E= array<Mint, 2>;
 static void mp(T &v, E x) { v= x[0] * v + x[1]; }
 static void cp(E &x, E y) { x= {y[0] * x[0], y[0] * x[1] + y[1]}; }
};
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 int N, Q;
 cin >> N >> Q;
 vector<Mint> a(N);
 for (int i= 0; i < N; i++) cin >> a[i];
 SegmentTree_Dynamic<M> seg(a);
 while (Q--) {
  int t;
  cin >> t;
  if (t) {
   int i;
   cin >> i;
   cout << seg[i] << '\n';
  } else {
   int l, r;
   Mint b, c;
   cin >> l >> r >> b >> c;
   seg.apply(l, r, {b, c});
  }
 }
 return 0;
}

#line 1 "test/yosupo/range_affine_point_get.DynSeg.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/range_affine_point_get
// competitive-verifier: TLE 1
// competitive-verifier: MLE 64
// 双対 の verify

#include <iostream>
#include <array>
#line 2 "src/Math/mod_inv.hpp"
#include <utility>
#include <type_traits>
#include <cassert>
template <class Uint> constexpr inline Uint mod_inv(Uint a, Uint mod) {
 std::make_signed_t<Uint> x= 1, y= 0, z= 0;
 for (Uint q= 0, b= mod, c= 0; b;) z= x, x= y, y= z - y * (q= a / b), c= a, a= b, b= c - b * q;
 return assert(a == 1), x < 0 ? mod - (-x) % mod : x % mod;
}
#line 2 "src/Internal/Remainder.hpp"
namespace math_internal {
using namespace std;
using u8= unsigned char;
using u32= unsigned;
using i64= long long;
using u64= unsigned long long;
using u128= __uint128_t;
struct MP_Na {  // mod < 2^32
 u32 mod;
 constexpr MP_Na(): mod(0) {}
 constexpr MP_Na(u32 m): mod(m) {}
 constexpr inline u32 mul(u32 l, u32 r) const { return u64(l) * r % mod; }
 constexpr inline u32 set(u32 n) const { return n; }
 constexpr inline u32 get(u32 n) const { return n; }
 constexpr inline u32 norm(u32 n) const { return n; }
 constexpr inline u32 plus(u64 l, u32 r) const { return l+= r, l < mod ? l : l - mod; }
 constexpr inline u32 diff(u64 l, u32 r) const { return l-= r, l >> 63 ? l + mod : l; }
};
template <class u_t, class du_t, u8 B> struct MP_Mo {  // mod < 2^32, mod < 2^62
 u_t mod;
 constexpr MP_Mo(): mod(0), iv(0), r2(0) {}
 constexpr MP_Mo(u_t m): mod(m), iv(inv(m)), r2(-du_t(mod) % mod) {}
 constexpr inline u_t mul(u_t l, u_t r) const { return reduce(du_t(l) * r); }
 constexpr inline u_t set(u_t n) const { return mul(n, r2); }
 constexpr inline u_t get(u_t n) const { return n= reduce(n), n >= mod ? n - mod : n; }
 constexpr inline u_t norm(u_t n) const { return n >= mod ? n - mod : n; }
 constexpr inline u_t plus(u_t l, u_t r) const { return l+= r, l < (mod << 1) ? l : l - (mod << 1); }
 constexpr inline u_t diff(u_t l, u_t r) const { return l-= r, l >> (B - 1) ? l + (mod << 1) : l; }
private:
 u_t iv, r2;
 static constexpr u_t inv(u_t n, int e= 6, u_t x= 1) { return e ? inv(n, e - 1, x * (2 - x * n)) : x; }
 constexpr inline u_t reduce(const du_t &w) const { return u_t(w >> B) + mod - ((du_t(u_t(w) * iv) * mod) >> B); }
};
using MP_Mo32= MP_Mo<u32, u64, 32>;
using MP_Mo64= MP_Mo<u64, u128, 64>;
struct MP_Br {  // 2^20 < mod <= 2^41
 u64 mod;
 constexpr MP_Br(): mod(0), x(0) {}
 constexpr MP_Br(u64 m): mod(m), x((u128(1) << 84) / m) {}
 constexpr inline u64 mul(u64 l, u64 r) const { return rem(u128(l) * r); }
 static constexpr inline u64 set(u64 n) { return n; }
 constexpr inline u64 get(u64 n) const { return n >= mod ? n - mod : n; }
 constexpr inline u64 norm(u64 n) const { return n >= mod ? n - mod : n; }
 constexpr inline u64 plus(u64 l, u64 r) const { return l+= r, l < (mod << 1) ? l : l - (mod << 1); }
 constexpr inline u64 diff(u64 l, u64 r) const { return l-= r, l >> 63 ? l + (mod << 1) : l; }
private:
 u64 x;
 constexpr inline u128 quo(const u128 &n) const { return (n * x) >> 84; }
 constexpr inline u64 rem(const u128 &n) const { return n - quo(n) * mod; }
};
template <class du_t, u8 B> struct MP_D2B1 {  // mod < 2^63, mod < 2^64
 u64 mod;
 constexpr MP_D2B1(): mod(0), s(0), d(0), v(0) {}
 constexpr MP_D2B1(u64 m): mod(m), s(__builtin_clzll(m)), d(m << s), v(u128(-1) / d) {}
 constexpr inline u64 mul(u64 l, u64 r) const { return rem((u128(l) * r) << s) >> s; }
 constexpr inline u64 set(u64 n) const { return n; }
 constexpr inline u64 get(u64 n) const { return n; }
 constexpr inline u64 norm(u64 n) const { return n; }
 constexpr inline u64 plus(du_t l, u64 r) const { return l+= r, l < mod ? l : l - mod; }
 constexpr inline u64 diff(du_t l, u64 r) const { return l-= r, l >> B ? l + mod : l; }
private:
 u8 s;
 u64 d, v;
 constexpr inline u64 rem(const u128 &u) const {
  u128 q= (u >> 64) * v + u;
  u64 r= u64(u) - (q >> 64) * d - d;
  if (r > u64(q)) r+= d;
  if (r >= d) r-= d;
  return r;
 }
};
using MP_D2B1_1= MP_D2B1<u64, 63>;
using MP_D2B1_2= MP_D2B1<u128, 127>;
template <class u_t, class MP> constexpr u_t pow(u_t x, u64 k, const MP &md) {
 for (u_t ret= md.set(1);; x= md.mul(x, x))
  if (k & 1 ? ret= md.mul(ret, x) : 0; !(k>>= 1)) return ret;
}
}
#line 3 "src/Internal/modint_traits.hpp"
namespace math_internal {
struct m_b {};
struct s_b: m_b {};
}
template <class mod_t> constexpr bool is_modint_v= std::is_base_of_v<math_internal::m_b, mod_t>;
template <class mod_t> constexpr bool is_staticmodint_v= std::is_base_of_v<math_internal::s_b, mod_t>;
#line 6 "src/Math/ModInt.hpp"
namespace math_internal {
template <class MP, u64 MOD> struct SB: s_b {
protected:
 static constexpr MP md= MP(MOD);
};
template <class U, class B> struct MInt: public B {
 using Uint= U;
 static constexpr inline auto mod() { return B::md.mod; }
 constexpr MInt(): x(0) {}
 template <class T, typename= enable_if_t<is_modint_v<T> && !is_same_v<T, MInt>>> constexpr MInt(T v): x(B::md.set(v.val() % B::md.mod)) {}
 constexpr MInt(__int128_t n): x(B::md.set((n < 0 ? ((n= (-n) % B::md.mod) ? B::md.mod - n : n) : n % B::md.mod))) {}
 constexpr MInt operator-() const { return MInt() - *this; }
#define FUNC(name, op) \
 constexpr MInt name const { \
  MInt ret; \
  return ret.x= op, ret; \
 }
 FUNC(operator+(const MInt & r), B::md.plus(x, r.x))
 FUNC(operator-(const MInt & r), B::md.diff(x, r.x))
 FUNC(operator*(const MInt & r), B::md.mul(x, r.x))
 FUNC(pow(u64 k), math_internal::pow(x, k, B::md))
#undef FUNC
 constexpr MInt operator/(const MInt &r) const { return *this * r.inv(); }
 constexpr MInt &operator+=(const MInt &r) { return *this= *this + r; }
 constexpr MInt &operator-=(const MInt &r) { return *this= *this - r; }
 constexpr MInt &operator*=(const MInt &r) { return *this= *this * r; }
 constexpr MInt &operator/=(const MInt &r) { return *this= *this / r; }
 constexpr bool operator==(const MInt &r) const { return B::md.norm(x) == B::md.norm(r.x); }
 constexpr bool operator!=(const MInt &r) const { return !(*this == r); }
 constexpr bool operator<(const MInt &r) const { return B::md.norm(x) < B::md.norm(r.x); }
 constexpr inline MInt inv() const { return mod_inv<U>(val(), B::md.mod); }
 constexpr inline Uint val() const { return B::md.get(x); }
 friend ostream &operator<<(ostream &os, const MInt &r) { return os << r.val(); }
 friend istream &operator>>(istream &is, MInt &r) {
  i64 v;
  return is >> v, r= MInt(v), is;
 }
private:
 Uint x;
};
template <u64 MOD> using MP_B= conditional_t < (MOD < (1 << 30)) & MOD, MP_Mo32, conditional_t < MOD < (1ull << 32), MP_Na, conditional_t<(MOD < (1ull << 62)) & MOD, MP_Mo64, conditional_t<MOD<(1ull << 41), MP_Br, conditional_t<MOD<(1ull << 63), MP_D2B1_1, MP_D2B1_2>>>>>;
template <u64 MOD> using ModInt= MInt < conditional_t<MOD<(1 << 30), u32, u64>, SB<MP_B<MOD>, MOD>>;
}
using math_internal::ModInt;
#line 3 "src/DataStructure/SegmentTree_Dynamic.hpp"
#include <vector>
#include <string>
#include <algorithm>
#include <tuple>
#include <cstddef>
#include <cstdint>
#line 3 "src/Internal/HAS_CHECK.hpp"
#define MEMBER_MACRO(member, Dummy, name, type1, type2, last) \
 template <class tClass> struct name##member { \
  template <class U, Dummy> static type1 check(U *); \
  static type2 check(...); \
  static tClass *mClass; \
  last; \
 }
#define HAS_CHECK(member, Dummy) MEMBER_MACRO(member, Dummy, has_, std::true_type, std::false_type, static const bool value= decltype(check(mClass))::value)
#define HAS_MEMBER(member) HAS_CHECK(member, int dummy= (&U::member, 0))
#define HAS_TYPE(member) HAS_CHECK(member, class dummy= typename U::member)
#define HOGE_OR(member, name, type2) \
 MEMBER_MACRO(member, class dummy= typename U::member, name, typename U::member, type2, using type= decltype(check(mClass))); \
 template <class tClass> using name##member##_t= typename name##member<tClass>::type
#define NULLPTR_OR(member) HOGE_OR(member, nullptr_or_, std::nullptr_t)
#define MYSELF_OR(member) HOGE_OR(member, myself_or_, tClass)
#line 10 "src/DataStructure/SegmentTree_Dynamic.hpp"
template <typename M, bool persistent= false, uint8_t HEIGHT= 31> class SegmentTree_Dynamic {
 HAS_MEMBER(op);
 HAS_MEMBER(ti);
 HAS_MEMBER(mp);
 HAS_MEMBER(cp);
 HAS_TYPE(T);
 HAS_TYPE(E);
 NULLPTR_OR(E);
 template <class L> static constexpr bool monoid_v= std::conjunction_v<has_T<L>, has_op<L>, has_ti<L>>;
 template <class L> static constexpr bool dual_v= std::conjunction_v<has_T<L>, has_E<L>, has_mp<L>, has_cp<L>>;
 using id_t= long long;
 template <class T, class tDerived> struct Node_B {
  T val;
  tDerived *ch[2]= {nullptr, nullptr};
 };
 template <bool mo, bool du, typename tEnable= void> struct Node_D: Node_B<M, Node_D<mo, du, tEnable>> {};
 template <bool mo, bool du> struct Node_D<mo, du, typename std::enable_if_t<mo && !du>>: Node_B<typename M::T, Node_D<mo, du>> {};
 template <bool mo, bool du> struct Node_D<mo, du, typename std::enable_if_t<du>>: Node_B<typename M::T, Node_D<mo, du>> {
  typename M::E lazy;
  bool lazy_flg= false;
 };
 using Node= Node_D<monoid_v<M>, dual_v<M>>;
 using T= decltype(Node::val);
 using E= nullptr_or_E_t<M>;
 using np= Node *;
 np root;
 static inline constexpr T def_val() {
  if constexpr (monoid_v<M>) return M::ti();
  else return T();
 }
 template <class S> np build(id_t n, id_t l, id_t r, const S &bg) {
  if (n <= l) return nullptr;
  if (r - l == 1) {
   if constexpr (std::is_same_v<S, T>) return new Node{bg};
   else return new Node{*(bg + l)};
  }
  id_t m= (r + l) / 2;
  np t= new Node{def_val(), {build(n, l, m, bg), build(n, m, r, bg)}};
  if constexpr (monoid_v<M>) update(t);
  return t;
 }
 void dump(np t, const id_t &l, const id_t &r, std::array<id_t, 2> b, typename std::vector<T>::iterator itr) {
  if (r <= b[0] || b[1] <= l) return;
  if (l <= b[0] && b[1] <= r && !t) {
   for (id_t i= b[0]; i < b[1]; i++) *(itr + i)= def_val();
  } else if (b[1] - b[0] != 1) {
   if constexpr (dual_v<M>) push(t, b[1] - b[0]);
   auto m= (b[0] + b[1]) >> 1;
   dump(t ? t->ch[0] : nullptr, l, r, {b[0], m}, itr);
   dump(t ? t->ch[1] : nullptr, l, r, {m, b[1]}, itr);
  } else *(itr + b[0])= t->val;
 }
 static inline void update(np &t) {
  t->val= def_val();
  if (t->ch[0]) t->val= M::op(t->ch[0]->val, t->val);
  if (t->ch[1]) t->val= M::op(t->val, t->ch[1]->val);
 }
 static inline void map(T &v, E x, int sz) {
  if constexpr (std::is_invocable_r_v<void, decltype(M::mp), T &, E, int>) M::mp(v, x, sz);
  else M::mp(v, x);
 }
 static inline T &reflect(np &t) {
  if constexpr (dual_v<M> && !monoid_v<M>)
   if (t->lazy_flg) map(t->val, t->lazy, 1), t->lazy_flg= false;
  return t->val;
 }
 static inline void propagate(np &t, const E &x, const id_t &sz) {
  t->lazy_flg ? (M::cp(t->lazy, x), x) : t->lazy= x;
  t->lazy_flg= true;
  if constexpr (monoid_v<M>) map(t->val, x, sz);
 }
 static inline void cp_node(np &t) {
  if (!t) t= new Node{def_val()};
  else if constexpr (persistent) t= new Node(*t);
 }
 static inline void push(np &t, const id_t &sz) {
  if (!t->lazy_flg) return;
  cp_node(t->ch[0]), cp_node(t->ch[1]), t->lazy_flg= false;
  propagate(t->ch[0], t->lazy, sz / 2), propagate(t->ch[1], t->lazy, sz / 2);
 }
 T prod(np &t, const id_t &l, const id_t &r, std::array<id_t, 2> b, const id_t &bias) {
  if (!t || r <= b[0] || b[1] <= l) return def_val();
  if (l <= b[0] && b[1] <= r) return t->val;
  if constexpr (dual_v<M>) push(t, b[1] - b[0]);
  id_t m= (b[0] + b[1]) >> 1;
  bool flg= (bias >> (__builtin_ctzll(b[1] - b[0]) - 1)) & 1;
  return M::op(prod(t->ch[flg], l, r, {b[0], m}, bias), prod(t->ch[!flg], l, r, {m, b[1]}, bias));
 }
 void apply(np &t, const id_t &l, const id_t &r, std::array<id_t, 2> b, const E &x) {
  if (r <= b[0] || b[1] <= l) return;
  id_t m= (b[0] + b[1]) >> 1;
  if (cp_node(t); l <= b[0] && b[1] <= r) return propagate(t, x, b[1] - b[0]);
  push(t, b[1] - b[0]);
  apply(t->ch[0], l, r, {b[0], m}, x), apply(t->ch[1], l, r, {m, b[1]}, x);
  if constexpr (monoid_v<M>) update(t);
 }
 void set_val(np &t, const id_t &k, const T &val, uint8_t h) {
  if (cp_node(t); !h) return reflect(t)= val, void();
  if constexpr (dual_v<M>) push(t, 1LL << h);
  set_val(t->ch[(k >> (h - 1)) & 1], k, val, h - 1);
  if constexpr (monoid_v<M>) update(t);
 }
 T &at_val(np &t, const id_t &k, uint8_t h) {
  if (cp_node(t); !h) return reflect(t);
  if constexpr (dual_v<M>) push(t, 1LL << h);
  return at_val(t->ch[(k >> (h - 1)) & 1], k, h - 1);
 }
 bool is_null(np &t, const id_t &k, uint8_t h) {
  if (!t) return true;
  if (!h) return false;
  if constexpr (dual_v<M>) push(t, 1LL << h);
  return is_null(t->ch[(k >> (h - 1)) & 1], k, h - 1);
 }
 T get_val(np &t, const id_t &k, uint8_t h) {
  if (!t) return def_val();
  if (!h) return reflect(t);
  if constexpr (dual_v<M>) push(t, 1LL << h);
  return get_val(t->ch[(k >> (h - 1)) & 1], k, h - 1);
 }
 template <bool last> static inline T calc_op(np &t, const T &v) {
  if constexpr (last) return M::op((t ? t->val : def_val()), v);
  else return M::op(v, (t ? t->val : def_val()));
 }
 template <bool last> static inline bool is_in(const id_t &m, const id_t &k) {
  if constexpr (last) return k <= m;
  else return m <= k;
 }
 template <bool last, class C, std::size_t N> static id_t find(const id_t &k, std::array<id_t, 2> b, const id_t &bias, uint8_t h, const C &check, std::array<np, N> &ts, std::array<T, N> &sums) {
  static_assert(monoid_v<M>, "\"find\" is not available\n");
  static std::array<T, N> sums2;
  if (std::all_of(ts.begin(), ts.end(), [](np t) { return !t; })) return -1;
  if (!h) {
   for (std::size_t i= N; i--;) sums[i]= calc_op<last>(ts[i], sums[i]);
   return std::apply(check, sums) ? std::get<last>(b) : -1;
  } else if (is_in<last>(k, b[0])) {
   for (std::size_t i= N; i--;) sums2[i]= calc_op<last>(ts[i], sums[i]);
   if (!std::apply(check, sums2)) return sums= std::move(sums2), -1;
  }
  if constexpr (dual_v<M>)
   for (std::size_t i= N; i--;) push(ts[i], b[1] - b[0]);
  std::array<np, N> ss;
  id_t m= (b[0] + b[1]) >> 1;
  bool flg= (bias >> (h - 1)) & 1;
  if (!is_in<last>(m, k)) {
   for (std::size_t i= N; i--;) ss[i]= ts[i] ? ts[i]->ch[flg] : nullptr;
   id_t ret= find<last>(k, {b[0], m}, bias, h - 1, check, ss, sums);
   if (ret >= 0) return ret;
  }
  for (std::size_t i= N; i--;) ss[i]= ts[i] ? ts[i]->ch[!flg] : nullptr;
  return find<last>(k, {m, b[1]}, bias, h - 1, check, ss, sums);
 }
public:
 SegmentTree_Dynamic(np t= nullptr): root(t) {}
 SegmentTree_Dynamic(std::size_t n, T val): root(build(n, 0, 1LL << HEIGHT, val)) {}
 SegmentTree_Dynamic(const T *bg, const T *ed): root(build(ed - bg, 0, 1LL << HEIGHT, bg)) {}
 SegmentTree_Dynamic(const std::vector<T> &ar): SegmentTree_Dynamic(ar.data(), ar.data() + ar.size()) {}
 void set(id_t k, T val) { set_val(root, k, val, HEIGHT); }
 T get(id_t k) { return get_val(root, k, HEIGHT); }
 bool is_null(id_t k) { return is_null(root, k, HEIGHT); }
 T &at(id_t k) {
  static_assert(!monoid_v<M>, "\"at\" is not available\n");
  return at_val(root, k, HEIGHT);
 }
 template <class L= M, std::enable_if_t<monoid_v<L>, std::nullptr_t> = nullptr> T operator[](id_t k) { return get(k); }
 template <class L= M, std::enable_if_t<!monoid_v<L>, std::nullptr_t> = nullptr> T &operator[](id_t k) { return at(k); }
 T prod(id_t a, id_t b, id_t bias= 0) {
  static_assert(monoid_v<M>, "\"prod\" is not available\n");
  return prod(root, a, b, {0, 1LL << HEIGHT}, bias);
 }
 // find i s.t.
 //  check(prod(a,i)) == False, check(prod(a,i+1)) == True
 // return -1 if not found
 template <class C> id_t find_first(id_t a, C check, id_t bias= 0) {
  std::array<T, 1> sum{def_val()};
  std::array<np, 1> t{root};
  return find<0>(a, {0, 1LL << HEIGHT}, bias, HEIGHT, check, t, sum);
 }
 template <std::size_t N, class C> static id_t find_first(id_t a, C check, std::array<SegmentTree_Dynamic, N> segs, id_t bias= 0) {
  std::array<T, N> sums;
  sums.fill(def_val());
  std::array<np, N> ts;
  for (std::size_t i= 0; i < N; i++) ts[i]= segs[i].root;
  return find<0>(a, {0, 1LL << HEIGHT}, bias, HEIGHT, check, ts, sums);
 }
 // find i s.t.
 //  check(prod(i+1,b)) == False, check(prod(i,b)) == True
 // return -1 if not found
 template <class C> id_t find_last(id_t b, C check, id_t bias= 0) {
  std::array<T, 1> sum{def_val()};
  std::array<np, 1> t{root};
  return find<1>(b, {1LL << HEIGHT, 0}, ~bias, HEIGHT, check, t, sum);
 }
 template <std::size_t N, class C> static id_t find_last(id_t b, C check, std::array<SegmentTree_Dynamic, N> segs, id_t bias= 0) {
  std::array<T, N> sums;
  sums.fill(def_val());
  std::array<np, N> ts;
  for (std::size_t i= 0; i < N; i++) ts[i]= segs[i].root;
  return find<1>(b, {1LL << HEIGHT, 0}, ~bias, HEIGHT, check, ts, sums);
 }
 void apply(id_t a, id_t b, E x) {
  static_assert(dual_v<M>, "\"apply\" is not available\n");
  apply(root, a, b, {0, 1LL << HEIGHT}, x);
 }
 std::vector<T> dump(id_t bg, id_t ed) {
  std::vector<T> ret(ed - bg);
  return dump(root, bg, ed, {0, 1LL << HEIGHT}, ret.begin()), ret;
 }
 static std::string which_available() {
  std::string ret= "";
  if constexpr (monoid_v<M>) ret+= "\"prod\" \"find\" ";
  else ret+= "\"at\" ";
  if constexpr (dual_v<M>) ret+= "\"apply\" ";
  return ret;
 }
};
#line 10 "test/yosupo/range_affine_point_get.DynSeg.test.cpp"
using namespace std;
using Mint= ModInt<998244353>;
struct M {
 using T= Mint;
 using E= array<Mint, 2>;
 static void mp(T &v, E x) { v= x[0] * v + x[1]; }
 static void cp(E &x, E y) { x= {y[0] * x[0], y[0] * x[1] + y[1]}; }
};
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 int N, Q;
 cin >> N >> Q;
 vector<Mint> a(N);
 for (int i= 0; i < N; i++) cin >> a[i];
 SegmentTree_Dynamic<M> seg(a);
 while (Q--) {
  int t;
  cin >> t;
  if (t) {
   int i;
   cin >> i;
   cout << seg[i] << '\n';
  } else {
   int l, r;
   Mint b, c;
   cin >> l >> r >> b >> c;
   seg.apply(l, r, {b, c});
  }
 }
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	example_00	AC	5 ms	4 MB
g++-13	max_random_00	AC	641 ms	52 MB
g++-13	max_random_01	AC	622 ms	52 MB
g++-13	max_random_02	AC	616 ms	52 MB
g++-13	random_00	AC	471 ms	41 MB
g++-13	random_01	AC	510 ms	49 MB
g++-13	random_02	AC	272 ms	9 MB
g++-13	small_00	AC	6 ms	3 MB
g++-13	small_01	AC	5 ms	4 MB
g++-13	small_02	AC	5 ms	4 MB
g++-13	small_03	AC	5 ms	4 MB
g++-13	small_04	AC	5 ms	3 MB
g++-13	small_05	AC	5 ms	3 MB
g++-13	small_06	AC	5 ms	4 MB
g++-13	small_07	AC	5 ms	4 MB
g++-13	small_08	AC	5 ms	4 MB
g++-13	small_09	AC	5 ms	4 MB
g++-13	small_random_00	AC	5 ms	4 MB
g++-13	small_random_01	AC	5 ms	4 MB
clang++-18	example_00	AC	5 ms	4 MB
clang++-18	max_random_00	AC	668 ms	52 MB
clang++-18	max_random_01	AC	668 ms	52 MB
clang++-18	max_random_02	AC	671 ms	52 MB
clang++-18	random_00	AC	518 ms	41 MB
clang++-18	random_01	AC	555 ms	49 MB
clang++-18	random_02	AC	305 ms	9 MB
clang++-18	small_00	AC	6 ms	4 MB
clang++-18	small_01	AC	5 ms	4 MB
clang++-18	small_02	AC	5 ms	4 MB
clang++-18	small_03	AC	5 ms	4 MB
clang++-18	small_04	AC	5 ms	4 MB
clang++-18	small_05	AC	5 ms	4 MB
clang++-18	small_06	AC	5 ms	4 MB
clang++-18	small_07	AC	5 ms	4 MB
clang++-18	small_08	AC	5 ms	4 MB
clang++-18	small_09	AC	5 ms	4 MB
clang++-18	small_random_00	AC	5 ms	4 MB
clang++-18	small_random_01	AC	5 ms	4 MB

Back to top page