test/segment_tree.test.cpp

View this file on GitHub
Last update: 2020-11-27 17:14:27+09:00
Problem: https://judge.yosupo.jp/problem/point_set_range_composite

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/point_set_range_composite"

#include "src/template.hpp"
#include "src/segment_tree.hpp"
#include "src/modint.hpp"

using modint = ModInt<998244353>;

struct Func{
  modint a, b;
  Func(ll a = 1, ll b = 0) : a(a), b(b) {};
  Func(modint a, modint b) : a(a), b(b) {};
};

struct F{
  using value_type = Func;

  Func operator()(const Func& l, const Func& r) const {
    return Func(r.a*l.a, r.a*l.b+r.b);
  }
  const Func ide = Func();
};

int main() {
  ll n, q;
  cin >> n >> q;
  SegmentTree<F> seg(n);

  vector<Func> vec(n);
  rep(i, n) {
    cin >> vec[i].a >> vec[i].b;
  }

  seg.build(vec);

  rep(i, q) {
    ll t, a, b, c;
    cin >> t >> a >> b >> c;
    if (t == 0) {
      seg.change(a, Func(b, c));
    } else {
      Func e = seg.query(a, b);
      cout << e.a*modint(c)+e.b << el;
    }
  }
}

#line 1 "test/segment_tree.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/point_set_range_composite"

#line 2 "src/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pl = pair<ll, ll>;
using vl = vector<ll>;
#define rep(i, n) for(ll i = 0; i < (ll)n; i++)
#define rep3(i, l, r) for(ll i = l; i < (ll)r; i++)
#define per(i, n) for(ll i = (ll)n-1; i >= 0; i--)
#define per3(i, l, r) for(ll i = (ll)r-1; i >= (ll)l; i--)
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
template<class T, class U> inline void cmax(T &a, U b) { if (a < b) a = b; }
template<class T, class U> inline void cmin(T &a, U b) { if (a > b) a = b; }
constexpr char el = '\n';
template<class T, class U> ostream &operator<<(ostream &os, const pair<T, U> &p) { os << p.first << " " << p.second; return os; }
template<class T, class U> istream &operator>>(istream &is, pair<T, U> &p) { is >> p.first >> p.second; return is; }
template<class T> ostream &operator<<(ostream &os, const vector<T> &v) { rep(i, v.size()) os << v[i] << (i+1 != (ll)v.size() ? " " : ""); return os; }
template<class T> istream &operator>>(istream &is, vector<T> &v) { for(T &i : v) is >> i; return is; }
struct IoSetup {
  IoSetup() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); cerr << fixed << setprecision(15); }
} io_setup;
#line 3 "src/segment_tree.hpp"

template<class Monoid>
struct SegmentTree {
  using T = typename Monoid::value_type;

  ll n;
  vector<T> tree;
  const Monoid ope;

  SegmentTree(ll n_) : n(n_) {
    tree.assign(2*n, ope.ide);
  }

  void build(const vector<T>& v) {
    rep(i, v.size())
      tree[i+n] = v[i];
    per(i, n)
      tree[i] = ope(tree[i*2], tree[i*2+1]);
  }

  void change(ll p, const T& x) {
    p += n;
    tree[p] = x;
    while (p >>= 1)
      tree[p] = ope(tree[p*2], tree[p*2+1]);
  }

  T query(ll l, ll r) const {
    T l_res{};
    T r_res{};
    for (l += n, r+= n; l < r; l >>= 1, r >>= 1) {
      if (l&1) l_res = ope(l_res, tree[l++]);
      if (r&1) r_res = ope(tree[--r], r_res);
    }
    return ope(l_res, r_res);
  }

  T operator[](ll i) {
    return tree[i+n];
  }
};
#line 3 "src/modint.hpp"

template <ll Mod>
struct ModInt {
  ll n;

  ModInt(const ll x = 0) : n(x) {
    while (n < 0) n += Mod;
    n %= Mod;
  }

  inline constexpr ModInt operator+(const ModInt r) const noexcept { return ModInt(*this) += r; }
  inline constexpr ModInt operator-(const ModInt r) const noexcept { return ModInt(*this) -= r; }
  inline constexpr ModInt operator*(const ModInt r) const noexcept { return ModInt(*this) *= r; }
  inline constexpr ModInt operator/(const ModInt r) const noexcept { return ModInt(*this) /= r; }
  inline constexpr ModInt &operator+=(const ModInt r) noexcept {
    n += r.n;
    if (n >= Mod) n -= Mod;
    return *this;
  }
  inline constexpr ModInt &operator-=(const ModInt r) noexcept {
    if (n < r.n) n += Mod;
    n -= r.n;
    return *this;
  }
  inline constexpr ModInt &operator*=(const ModInt r) noexcept {
    n = n * r.n % Mod;
    return *this;
  }
  inline constexpr ModInt &operator/=(const ModInt r) noexcept { return *this *= r.inv(); }

  inline constexpr ModInt pow(ll x) const noexcept {
    ModInt<Mod> ret(1), tmp(*this);
    while (x) {
      if (x&1) ret *= tmp;
      tmp *= tmp;
      x >>= 1;
    }
    return ret;
  }
  inline constexpr ModInt inv() const noexcept { return pow(Mod-2); }

  friend ostream& operator<<(ostream& os, const ModInt& obj) { return os << obj.n; }
  friend istream& operator>>(istream& is, ModInt& obj) {
    ll t;
    is >> t;
    obj = ModInt(t);
    return is;
  }
};

constexpr ll mod = 1000000007;
using mint = ModInt<mod>;
mint operator"" _mi(unsigned long long n) { return mint(n); }
#line 6 "test/segment_tree.test.cpp"

using modint = ModInt<998244353>;

struct Func{
  modint a, b;
  Func(ll a = 1, ll b = 0) : a(a), b(b) {};
  Func(modint a, modint b) : a(a), b(b) {};
};

struct F{
  using value_type = Func;

  Func operator()(const Func& l, const Func& r) const {
    return Func(r.a*l.a, r.a*l.b+r.b);
  }
  const Func ide = Func();
};

int main() {
  ll n, q;
  cin >> n >> q;
  SegmentTree<F> seg(n);

  vector<Func> vec(n);
  rep(i, n) {
    cin >> vec[i].a >> vec[i].b;
  }

  seg.build(vec);

  rep(i, q) {
    ll t, a, b, c;
    cin >> t >> a >> b >> c;
    if (t == 0) {
      seg.change(a, Func(b, c));
    } else {
      Func e = seg.query(a, b);
      cout << e.a*modint(c)+e.b << el;
    }
  }
}