test/Library_Checker/Data_Structure/Point_Set_Range_Composite.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/segmenttree.hpp

Code

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

#include <iostream>
#include "data_structure/segmenttree.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::SegmentTree<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_Composite.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/point_set_range_composite"

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

#include <cassert>
#include <vector>
#include <functional>

namespace ayuna {

template <class S, auto op, auto e> struct SegmentTree {
  SegmentTree(int n) : SegmentTree(std::vector<S>(n, e())) {}
  SegmentTree(const std::vector<S> &v) : _n(v.size()) {
    size = bit_ceil((unsigned int)_n);
    log = __builtin_ctz((unsigned int)size);
    d.resize(size << 1, e());
    for (int i = 0; i < _n; i++) d[size + i] = v[i];
    for (int i = size - 1; i >= 1; i--) update(i);
  }

  void set(int p, S x){
    assert(0 <= p && p < _n);
    p += size;
    d[p] = x;
    for (int i = 1; i <= log; i++) update(p >> i);
  }

  S get(const int p) const{
    assert(0 <= p && p < _n);
    return d[p + size];
  }

  S prod(int l, int r) const{
    assert(0 <= l && l <= r && r <= _n);
    S sml = e(), smr = e();
    l += size;
    r += size;
    while (l < r) {
      if (l & 1) sml = op(sml, d[l++]);
      if (r & 1) smr = op(d[--r], smr);
      l >>= 1;
      r >>= 1;
    }
    return op(sml, smr);
  }

  S all_prod() const{
    return d[1];
  }

private:
  int _n, size, log;
  std::vector<S> d;
  void update(int i) { d[i] = op(d[i << 1], d[i << 1 | 1]); }

  unsigned int bit_ceil(unsigned int n) {
    unsigned int x = 1;
    while (x < (unsigned int)(n)) x <<= 1;
    return x;
  }
};

} // namespace ayuna
#line 5 "test/Library_Checker/Data_Structure/Point_Set_Range_Composite.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::SegmentTree<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