test/ds/dynlzsgt.test.cpp

View this file on GitHub
Last update: 2026-02-18 18:32:54+08:00
Problem: https://judge.yosupo.jp/problem/range_affine_range_sum

Depends on

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/range_affine_range_sum
#include <bits/stdc++.h>
#define PUSHB push_back
using namespace std;
using ll = long long;
using ull = unsigned long long;

#include "../../src/ds/dynlzsgt.hpp"
#include "../../src/math/modint.hpp"
#include "../../src/misc/read.hpp"

struct Info_ {
  mint sum = 0;
  friend Info_ operator+(const Info_& lhs, const Info_& rhs) {
    return {lhs.sum + rhs.sum};
  }
};
struct Tag_ {
  mint b = 1, c = 0;
  Tag_ operator+=(const Tag_& rhs) {
    b *= rhs.b;
    c = c * rhs.b + rhs.c;
    return *this;
  }
};
void fn_(Info_& x, const Tag_& f, int len) { x.sum = x.sum * f.b + f.c * len; }

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n = read(), q = read();
  SegTree<Info_, Tag_, fn_> sgt(n);
  for (int i = 0; i < n; i++) {
    int x = read();
    sgt.set(i, {x});
  }
  while (q--) {
    int op = read(), l = read(), r = read();
    if (op == 0) {
      int b = read(), c = read();
      sgt.apply(l, r, {b, c});
    } else {
      cout << sgt.sum(l, r).sum.data << "\n";
    }
  }
  return 0;
}

#line 1 "test/ds/dynlzsgt.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/range_affine_range_sum
#include <bits/stdc++.h>
#define PUSHB push_back
using namespace std;
using ll = long long;
using ull = unsigned long long;

#line 1 "src/ds/dynlzsgt.hpp"
template <typename Info, typename Tag, void (*fn)(Info&, const Tag&, int)>
struct SegTree {
  struct Node {
    Info info = {};
    Tag tag = {};
    int ls = -1, rs = -1;
  };
  int n, _pos, _l, _r, root;
  Info _v;
  Tag _f;
  vector<Node> tree;
  SegTree(int n) : n(n) { root = alloc({}); }
  void set(int pos, Info v) { _pos = pos, _v = v, set(root, 0, n); }
  void apply(int l, int r, Tag f) { _l = l, _r = r, _f = f, apply(root, 0, n); }
  Info sum(int l, int r) { return _l = l, _r = r, sum(root, 0, n); }

 private:
  int alloc(Node node) { return tree.PUSHB(move(node)), int(tree.size()) - 1; }
  void update(int p, const Tag& f, int len) {
    fn(tree[p].info, f, len), tree[p].tag += f;
  }
  void pushdown(int p, int pl, int pr) {
    int mid = pl + (pr - pl) / 2, lenl = mid - pl, lenr = pr - mid;
    update(tree[p].ls, tree[p].tag, lenl);
    update(tree[p].rs, tree[p].tag, lenr);
    tree[p].tag = {};
  }
  void set(int p, int pl, int pr) {
    if (pr - pl == 1) return tree[p].info = _v, tree[p].tag = {}, void();
    int ls = tree[p].ls, rs = tree[p].rs, mid = pl + (pr - pl) / 2;
    if (ls == -1) ls = tree[p].ls = alloc({});
    if (rs == -1) rs = tree[p].rs = alloc({});
    pushdown(p, pl, pr), _pos < mid ? set(ls, pl, mid) : set(rs, mid, pr);
    tree[p].info = tree[ls].info + tree[rs].info;
  }
  void apply(int p, int pl, int pr) {
    if (_r <= pl || pr <= _l || p == -1) return;
    if (_l <= pl && pr <= _r) return update(p, _f, pr - pl);
    int ls = tree[p].ls, rs = tree[p].rs, mid = pl + (pr - pl) / 2;
    if (ls == -1) ls = tree[p].ls = alloc({});
    if (rs == -1) rs = tree[p].rs = alloc({});
    pushdown(p, pl, pr), apply(ls, pl, mid), apply(rs, mid, pr);
    tree[p].info = tree[ls].info + tree[rs].info;
  }
  Info sum(int p, int pl, int pr) {
    if (_r <= pl || pr <= _l || p == -1) return {};
    if (_l <= pl && pr <= _r) return tree[p].info;
    int ls = tree[p].ls, rs = tree[p].rs, mid = pl + (pr - pl) / 2;
    if (ls == -1) ls = tree[p].ls = alloc({});
    if (rs == -1) rs = tree[p].rs = alloc({});
    return pushdown(p, pl, pr), sum(ls, pl, mid) + sum(rs, mid, pr);
  }
};
struct Info {
  ll sum = 0;
  friend Info operator+(const Info& lhs, const Info& rhs) {
    return {lhs.sum + rhs.sum};
  }
};
struct Tag {
  bool set = 0;
  Tag& operator+=(const Tag& rhs) {
    set |= rhs.set;
    return *this;
  }
};
void fn(Info& x, const Tag& f, int len) {
  if (f.set) {
    x.sum = len;
  }
}
#line 1 "src/math/modint.hpp"
template <unsigned MOD>
struct ModInt {
  unsigned data;
  ModInt(ll v = 0) : data(norm(v % MOD)) {}
  ModInt operator-() const { return MOD - data; }
  ModInt& operator+=(ModInt rhs) { return data = norm(data + rhs.data), *this; }
  ModInt& operator-=(ModInt rhs) { return data = norm(data - rhs.data), *this; }
  ModInt& operator*=(ModInt rhs) {
    return data = ull(data) * rhs.data % MOD, *this;
  }
  ModInt& operator/=(ModInt rhs) {
    return data = ull(data) * rhs.inv() % MOD, *this;
  }
  friend ModInt operator+(ModInt lhs, ModInt rhs) { return lhs += rhs; }
  friend ModInt operator-(ModInt lhs, ModInt rhs) { return lhs -= rhs; }
  friend ModInt operator*(ModInt lhs, ModInt rhs) { return lhs *= rhs; }
  friend ModInt operator/(ModInt lhs, ModInt rhs) { return lhs /= rhs; }
  unsigned inv() const {
    ll x, y;  // Inverse does not exist if gcd(data, MOD) != 1.
    assert(exgcd(data, MOD, x, y) == 1);
    return norm(x);
  }
  ModInt pow(ull n) const { return pow_mod(data, n, MOD); }
  static ll exgcd(ll a, ll b, ll& x, ll& y) {
    x = 1, y = 0;
    ll x1 = 0, y1 = 1;
    while (b) {
      ll q = a / b;
      swap(a -= q * b, b);
      swap(x -= q * x1, x1);
      swap(y -= q * y1, y1);
    }
    return a;
  }
  static unsigned pow_mod(unsigned a, ull n, unsigned p) {
    unsigned ret = 1;
    for (; n; n /= 2) {
      if (n & 1) ret = ull(ret) * a % p;
      a = ull(a) * a % p;
    }
    return ret;
  }

 private:
  static unsigned norm(unsigned x) {
    if ((x >> (8 * sizeof(unsigned) - 1)) & 1) x += MOD;
    return x >= MOD ? x -= MOD : x;
  }
};
constexpr unsigned MOD = 998244353;
using mint = ModInt<MOD>;
#line 1 "src/misc/read.hpp"
#define GC ch = getchar_unlocked()
ll read() {
  ll x = 0, f = 1, GC;
  while (ch < '0' || ch > '9') ch == '-' ? f = -1, GC : GC;
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', GC;
  return x * f;
}
#undef GC
#line 11 "test/ds/dynlzsgt.test.cpp"

struct Info_ {
  mint sum = 0;
  friend Info_ operator+(const Info_& lhs, const Info_& rhs) {
    return {lhs.sum + rhs.sum};
  }
};
struct Tag_ {
  mint b = 1, c = 0;
  Tag_ operator+=(const Tag_& rhs) {
    b *= rhs.b;
    c = c * rhs.b + rhs.c;
    return *this;
  }
};
void fn_(Info_& x, const Tag_& f, int len) { x.sum = x.sum * f.b + f.c * len; }

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n = read(), q = read();
  SegTree<Info_, Tag_, fn_> sgt(n);
  for (int i = 0; i < n; i++) {
    int x = read();
    sgt.set(i, {x});
  }
  while (q--) {
    int op = read(), l = read(), r = read();
    if (op == 0) {
      int b = read(), c = read();
      sgt.apply(l, r, {b, c});
    } else {
      cout << sgt.sum(l, r).sum.data << "\n";
    }
  }
  return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	5 ms	4 MB
g++	max_random_00	AC	723 ms	25 MB
g++	max_random_01	AC	738 ms	25 MB
g++	max_random_02	AC	736 ms	25 MB
g++	random_00	AC	566 ms	25 MB
g++	random_01	AC	615 ms	25 MB
g++	random_02	AC	336 ms	6 MB
g++	small_00	AC	5 ms	4 MB
g++	small_01	AC	4 ms	4 MB
g++	small_02	AC	4 ms	4 MB
g++	small_03	AC	5 ms	4 MB
g++	small_04	AC	5 ms	4 MB
g++	small_05	AC	5 ms	4 MB
g++	small_06	AC	4 ms	4 MB
g++	small_07	AC	4 ms	4 MB
g++	small_08	AC	4 ms	4 MB
g++	small_09	AC	4 ms	3 MB
g++	small_random_00	AC	5 ms	4 MB
g++	small_random_01	AC	5 ms	4 MB