test/Library_Checker/Data_Structure/Point_Set_Range_Composite2.test.cpp

• View this file on GitHub
• Last update: 2026-05-07 01:17:17+09:00
• Problem: https://judge.yosupo.jp/problem/point_set_range_composite

Depends on

• data_structure/dynamicsegtree.hpp

Code

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

#include <iostream>
#include "data_structure/dynamicsegtree.hpp"
using namespace std;
using ll = long long;

constexpr ll m93 = 998244353ll;
pair<ll, ll> op(pair<ll, ll> a, pair<ll, ll> b) { return make_pair(a.first * b.first % m93, (a.second * b.first % m93 + b.second) % m93);}
pair<ll, ll> e() { return make_pair(1ll, 0ll);}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  int n, q;
  cin >> n >> q;
  ayuna::DynamicSegmentTree<pair<ll, ll>, op, e> st(n);
  for (int i = 0; i < n; i++) {
    int c, d;
    cin >> c >> d;
    st.set(i, make_pair(c, d));
  }
  while (q--) {
    int num;
    cin >> num;
    switch (num) {
      case 0:{
        int p;
        ll c, d;
        cin >> p >> c >> d;
        st.set(p, make_pair(c, d));
        break;
      }
      case 1:{
        int l, r;
        ll x;
        cin >> l >> r >> x;
        auto [c, d] = st.prod(l, r);
        cout << (c * x % m93 + d) % m93 << endl;
        break;
      }
    }
  }
}

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

#include <iostream>
#line 2 "data_structure/dynamicsegtree.hpp"

#include <cassert>
#include <memory>

namespace ayuna {

template <class S, S (*op)(S, S), S (*e)()>
class DynamicSegmentTree {
public:
  DynamicSegmentTree(long long _n) : n(_n), root(nullptr) {}

  void set(long long p, S x) {
    assert(p < n);
    set(root, 0, n, p, x);
  }
  S get(long long p) const {
    assert(p < n);
    return get(root, 0, n, p);
  }
  S prod(long long l, long long r) const {
    assert(l <= r && r <= n);
    return prod(root, 0, n, l, r);
  }

  S all_prod() const { return root ? root->value : e(); }

  void reset(long long l, long long r) {
    assert(l <= r && r <= n);
    reset(root, 0, n, l, r);
  }

private:
  struct node;
  using node_ptr = std::unique_ptr<node>;

  struct node {
    S value;
    node_ptr left, right;
    node() : value(e()), left(nullptr), right(nullptr) {}
    node(S v) : value(v), left(nullptr), right(nullptr) {}
  };

  long long n;
  node_ptr root;

  void set(node_ptr &t, long long l, long long r, long long p, S x) {
    if(t == nullptr)
      t = std::make_unique<node>();
    if(r - l == 1) {
      t->value = x;
      return;
    }
    long long m = (l + r) >> 1;
    if(p < m)
      set(t->left, l, m, p, x);
    else
      set(t->right, m, r, p, x);
    t->value =
        op(t->left ? t->left->value : e(), t->right ? t->right->value : e());
  }

  S get(const node_ptr &t, long long l, long long r, long long p) const {
    if(t == nullptr)
      return e();
    if(r - l == 1)
      return t->value;
    long long m = (l + r) >> 1;
    if(p < m)
      return get(t->left, l, m, p);
    else
      return get(t->right, m, r, p);
  }

  S prod(const node_ptr &t, long long l, long long r, long long ql,
         long long qr) const {
    if(t == nullptr || r <= ql || qr <= l)
      return e();
    if(ql <= l && r <= qr)
      return t->value;
    long long m = (l + r) >> 1;
    return op(prod(t->left, l, m, ql, qr), prod(t->right, m, r, ql, qr));
  }

  void reset(node_ptr &t, long long l, long long r, long long ql,
             long long qr) {
    if(t == nullptr || r <= ql || qr <= l)
      return;
    if(ql <= l && r <= qr) {
      t.reset();
      return;
    }
    long long m = (l + r) >> 1;
    reset(t->left, l, m, ql, qr);
    reset(t->right, m, r, ql, qr);
    t->value =
        op(t->left ? t->left->value : e(), t->right ? t->right->value : e());
  }
};

} // namespace ayuna
#line 5 "test/Library_Checker/Data_Structure/Point_Set_Range_Composite2.test.cpp"
using namespace std;
using ll = long long;

constexpr ll m93 = 998244353ll;
pair<ll, ll> op(pair<ll, ll> a, pair<ll, ll> b) { return make_pair(a.first * b.first % m93, (a.second * b.first % m93 + b.second) % m93);}
pair<ll, ll> e() { return make_pair(1ll, 0ll);}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  int n, q;
  cin >> n >> q;
  ayuna::DynamicSegmentTree<pair<ll, ll>, op, e> st(n);
  for (int i = 0; i < n; i++) {
    int c, d;
    cin >> c >> d;
    st.set(i, make_pair(c, d));
  }
  while (q--) {
    int num;
    cin >> num;
    switch (num) {
      case 0:{
        int p;
        ll c, d;
        cin >> p >> c >> d;
        st.set(p, make_pair(c, d));
        break;
      }
      case 1:{
        int l, r;
        ll x;
        cin >> l >> r >> x;
        auto [c, d] = st.prod(l, r);
        cout << (c * x % m93 + d) % m93 << endl;
        break;
      }
    }
  }
}

Back to top page