firiexp's Library
This documentation is automatically generated by online-judge-tools/verification-helper
test/yosupo_dynamic_sequence_range_affine_range_sum.test.cpp
- View this file on GitHub
- Last update: 2026-03-22 13:47:31+09:00
- Problem: https://judge.yosupo.jp/problem/dynamic_sequence_range_affine_range_sum
Depends on
- Implicit Treap
(datastructure/implicit_treap.cpp)
- 高速入出力(Fast IO)
(util/fastio.cpp)
- modint(固定MOD)
(util/modint.cpp)
Code
#define PROBLEM "https://judge.yosupo.jp/problem/dynamic_sequence_range_affine_range_sum"
#include <algorithm>
#include <array>
#include <vector>
using namespace std;
static const int MOD = 998244353;
using ll = long long;
using uint = unsigned;
using ull = unsigned long long;
#include <cstdio>
#include <cstring>
#include <string>
#include <type_traits>
#include "../util/fastio.cpp"
#include "../util/modint.cpp"
#include "../datastructure/implicit_treap.cpp"
struct AffineSumMonoid {
using T = array<mint, 2>;
using L = array<mint, 2>;
static T f(T a, T b) { return {a[0] + b[0], a[1] + b[1]}; }
static T g(T a, L b) { return {a[0] * b[0] + a[1] * b[1], a[1]}; }
static L h(L a, L b) { return {a[0] * b[0], a[1] * b[0] + b[1]}; }
static T e() { return {0, 0}; }
static L l() { return {1, 0}; }
};
int main() {
Scanner sc;
Printer pr;
int n, q;
sc.read(n, q);
vector<array<mint, 2>> init(n);
for (int i = 0; i < n; ++i) {
int a;
sc.read(a);
init[i] = {a, 1};
}
ImplicitTreap<AffineSumMonoid> tr(init);
tr.reserve(n + q);
while (q--) {
int t;
sc.read(t);
if (t == 0) {
int pos, x;
sc.read(pos, x);
tr.insert(pos, {x, 1});
} else if (t == 1) {
int pos;
sc.read(pos);
tr.erase(pos);
} else if (t == 2) {
int l, r;
sc.read(l, r);
tr.reverse(l, r);
} else if (t == 3) {
int l, r, b, c;
sc.read(l, r, b, c);
tr.apply(l, r, {b, c});
} else {
int l, r;
sc.read(l, r);
pr.println(tr.fold(l, r)[0].val);
}
}
return 0;
}#line 1 "test/yosupo_dynamic_sequence_range_affine_range_sum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/dynamic_sequence_range_affine_range_sum"
#include <algorithm>
#include <array>
#include <vector>
using namespace std;
static const int MOD = 998244353;
using ll = long long;
using uint = unsigned;
using ull = unsigned long long;
#include <cstdio>
#include <cstring>
#include <string>
#include <type_traits>
#line 1 "util/fastio.cpp"
using namespace std;
extern "C" int fileno(FILE *);
extern "C" int isatty(int);
template<class T, class = void>
struct is_fastio_range : false_type {};
template<class T>
struct is_fastio_range<T, void_t<decltype(declval<T &>().begin()), decltype(declval<T &>().end())>> : true_type {};
template<class T, class = void>
struct has_fastio_value : false_type {};
template<class T>
struct has_fastio_value<T, void_t<decltype(declval<const T &>().value())>> : true_type {};
struct FastIoDigitTable {
char num[40000];
constexpr FastIoDigitTable() : num() {
for (int i = 0; i < 10000; ++i) {
int x = i;
for (int j = 3; j >= 0; --j) {
num[i * 4 + j] = char('0' + x % 10);
x /= 10;
}
}
}
};
struct Scanner {
static constexpr int BUFSIZE = 1 << 17;
static constexpr int OFFSET = 64;
char buf[BUFSIZE + 1];
int idx, size;
bool interactive;
Scanner() : idx(0), size(0), interactive(isatty(fileno(stdin))) {}
inline void load() {
int len = size - idx;
memmove(buf, buf + idx, len);
if (interactive) {
if (fgets(buf + len, BUFSIZE + 1 - len, stdin)) size = len + (int)strlen(buf + len);
else size = len;
} else {
size = len + (int)fread(buf + len, 1, BUFSIZE - len, stdin);
}
idx = 0;
buf[size] = 0;
}
inline void ensure() {
if (idx + OFFSET > size) load();
}
inline void ensure_interactive() {
if (idx == size) load();
}
inline char skip() {
if (interactive) {
ensure_interactive();
while (buf[idx] && buf[idx] <= ' ') {
++idx;
ensure_interactive();
}
return buf[idx++];
}
ensure();
while (buf[idx] && buf[idx] <= ' ') {
++idx;
ensure();
}
return buf[idx++];
}
template<class T, typename enable_if<is_integral<T>::value, int>::type = 0>
void read(T &x) {
if (interactive) {
char c = skip();
bool neg = false;
if constexpr (is_signed<T>::value) {
if (c == '-') {
neg = true;
ensure_interactive();
c = buf[idx++];
}
}
x = 0;
while (c >= '0') {
x = x * 10 + (c & 15);
ensure_interactive();
c = buf[idx++];
}
if constexpr (is_signed<T>::value) {
if (neg) x = -x;
}
return;
}
char c = skip();
bool neg = false;
if constexpr (is_signed<T>::value) {
if (c == '-') {
neg = true;
c = buf[idx++];
}
}
x = 0;
while (c >= '0') {
x = x * 10 + (c & 15);
c = buf[idx++];
}
if constexpr (is_signed<T>::value) {
if (neg) x = -x;
}
}
template<class T, typename enable_if<!is_integral<T>::value && !is_fastio_range<T>::value && !is_same<typename decay<T>::type, string>::value && has_fastio_value<T>::value, int>::type = 0>
void read(T &x) {
long long v;
read(v);
x = T(v);
}
template<class Head, class Next, class... Tail>
void read(Head &head, Next &next, Tail &...tail) {
read(head);
read(next, tail...);
}
template<class T, class U>
void read(pair<T, U> &p) {
read(p.first, p.second);
}
template<class T, typename enable_if<is_fastio_range<T>::value && !is_same<typename decay<T>::type, string>::value, int>::type = 0>
void read(T &a) {
for (auto &x : a) read(x);
}
void read(char &c) {
c = skip();
}
void read(string &s) {
s.clear();
if (interactive) {
ensure_interactive();
while (buf[idx] && buf[idx] <= ' ') {
++idx;
ensure_interactive();
}
while (true) {
int start = idx;
while (idx < size && buf[idx] > ' ') ++idx;
s.append(buf + start, idx - start);
if (idx < size) break;
load();
if (size == 0) break;
}
if (idx < size) ++idx;
return;
}
ensure();
while (buf[idx] && buf[idx] <= ' ') {
++idx;
ensure();
}
while (true) {
int start = idx;
while (idx < size && buf[idx] > ' ') ++idx;
s.append(buf + start, idx - start);
if (idx < size) break;
load();
}
if (idx < size) ++idx;
}
};
struct Printer {
static constexpr int BUFSIZE = 1 << 17;
static constexpr int OFFSET = 64;
char buf[BUFSIZE];
int idx;
bool interactive;
inline static constexpr FastIoDigitTable table{};
Printer() : idx(0), interactive(isatty(fileno(stdout))) {}
~Printer() { flush(); }
inline void flush() {
if (idx) {
fwrite(buf, 1, idx, stdout);
idx = 0;
}
}
inline void pc(char c) {
if (idx > BUFSIZE - OFFSET) flush();
buf[idx++] = c;
if (interactive && c == '\n') flush();
}
inline void print_range(const char *s, size_t n) {
size_t pos = 0;
while (pos < n) {
if (idx == BUFSIZE) flush();
size_t chunk = min(n - pos, (size_t)(BUFSIZE - idx));
memcpy(buf + idx, s + pos, chunk);
idx += (int)chunk;
pos += chunk;
}
}
void print(const char *s) {
print_range(s, strlen(s));
}
void print(const string &s) {
print_range(s.data(), s.size());
}
void print(char c) {
pc(c);
}
void print(bool b) {
pc(char('0' + (b ? 1 : 0)));
}
template<class T, typename enable_if<is_integral<T>::value && !is_same<T, bool>::value, int>::type = 0>
void print(T x) {
if (idx > BUFSIZE - 100) flush();
using U = typename make_unsigned<T>::type;
U y;
if constexpr (is_signed<T>::value) {
if (x < 0) {
buf[idx++] = '-';
y = U(0) - static_cast<U>(x);
} else {
y = static_cast<U>(x);
}
} else {
y = x;
}
if (y == 0) {
buf[idx++] = '0';
return;
}
static constexpr int TMP_SIZE = sizeof(U) * 10 / 4;
char tmp[TMP_SIZE];
int pos = TMP_SIZE;
while (y >= 10000) {
pos -= 4;
memcpy(tmp + pos, table.num + (y % 10000) * 4, 4);
y /= 10000;
}
if (y >= 1000) {
memcpy(buf + idx, table.num + (y << 2), 4);
idx += 4;
} else if (y >= 100) {
memcpy(buf + idx, table.num + (y << 2) + 1, 3);
idx += 3;
} else if (y >= 10) {
unsigned q = (unsigned(y) * 205) >> 11;
buf[idx] = char('0' + q);
buf[idx + 1] = char('0' + (unsigned(y) - q * 10));
idx += 2;
} else {
buf[idx++] = char('0' + y);
}
memcpy(buf + idx, tmp + pos, TMP_SIZE - pos);
idx += TMP_SIZE - pos;
}
template<class T, typename enable_if<!is_integral<T>::value && !is_fastio_range<T>::value && !is_same<typename decay<T>::type, string>::value && has_fastio_value<T>::value, int>::type = 0>
void print(const T &x) {
print(x.value());
}
template<class T, typename enable_if<is_fastio_range<T>::value && !is_same<typename decay<T>::type, string>::value, int>::type = 0>
void print(const T &a) {
bool first = true;
for (auto &&x : a) {
if (!first) pc(' ');
first = false;
print(x);
}
}
template<class T>
void println(const T &x) {
print(x);
pc('\n');
}
template<class Head, class... Tail>
void println(const Head &head, const Tail &...tail) {
print(head);
((pc(' '), print(tail)), ...);
pc('\n');
}
void println() {
pc('\n');
}
};
template<class T>
Scanner &operator>>(Scanner &in, T &x) {
in.read(x);
return in;
}
template<class T>
Printer &operator<<(Printer &out, const T &x) {
out.print(x);
return out;
}
/**
* @brief 高速入出力(Fast IO)
*/
#line 1 "util/modint.cpp"
template <uint Mod>
struct modint {
uint val;
public:
static modint raw(int v) { modint x; x.val = v; return x; }
static constexpr uint get_mod() { return Mod; }
static constexpr uint M() { return Mod; }
modint() : val(0) {}
template <class T>
modint(T v) { ll x = (ll)(v % (ll)(Mod)); if (x < 0) x += Mod; val = uint(x); }
modint(bool v) { val = ((unsigned int)(v) % Mod); }
uint &value() noexcept { return val; }
const uint &value() const noexcept { return val; }
modint& operator++() { val++; if (val == Mod) val = 0; return *this; }
modint& operator--() { if (val == 0) val = Mod; val--; return *this; }
modint operator++(int) { modint result = *this; ++*this; return result; }
modint operator--(int) { modint result = *this; --*this; return result; }
modint& operator+=(const modint& b) { val += b.val; if (val >= Mod) val -= Mod; return *this; }
modint& operator-=(const modint& b) { val -= b.val; if (val >= Mod) val += Mod; return *this; }
modint& operator*=(const modint& b) { ull z = val; z *= b.val; val = (uint)(z % Mod); return *this; }
modint& operator/=(const modint& b) { return *this = *this * b.inv(); }
modint operator+() const { return *this; }
modint operator-() const { return modint() - *this; }
modint pow(long long n) const { modint x = *this, r = 1; while (n) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
modint inv() const { return pow(Mod - 2); }
friend modint operator+(const modint& a, const modint& b) { return modint(a) += b; }
friend modint operator-(const modint& a, const modint& b) { return modint(a) -= b; }
friend modint operator*(const modint& a, const modint& b) { return modint(a) *= b; }
friend modint operator/(const modint& a, const modint& b) { return modint(a) /= b; }
friend bool operator==(const modint& a, const modint& b) { return a.val == b.val; }
friend bool operator!=(const modint& a, const modint& b) { return a.val != b.val; }
};
using mint = modint<MOD>;
#define FIRIEXP_LIBRARY_MINT_ALIAS_DEFINED
/**
* @brief modint(固定MOD)
*/
#line 1 "datastructure/implicit_treap.cpp"
template <class M>
struct ImplicitTreap {
using T = typename M::T;
using L = typename M::L;
struct Node {
int l, r, sz;
unsigned pri;
bool rev, has_lazy;
T val, sum, rsum;
L lazy;
Node(unsigned pri, const T &val)
: l(-1), r(-1), sz(1), pri(pri), rev(false), has_lazy(false),
val(val), sum(val), rsum(val), lazy(M::l()) {}
};
int root;
vector<Node> nodes;
vector<int> free_nodes;
unsigned long long rng_state;
ImplicitTreap() : root(-1), rng_state(0x123456789abcdef0ull) {}
explicit ImplicitTreap(const vector<T> &v) : ImplicitTreap() {
reserve((int)v.size());
build_linear(v);
}
int size() const {
return root == -1 ? 0 : nodes[root].sz;
}
bool empty() const {
return root == -1;
}
void reserve(int capacity) {
nodes.reserve(capacity);
free_nodes.reserve(capacity);
}
T all_fold() const {
return root == -1 ? M::e() : nodes[root].sum;
}
void insert(int k, const T &x) {
auto [a, b] = split(root, k);
root = merge(merge(a, new_node(x)), b);
}
void push_front(const T &x) {
insert(0, x);
}
void push_back(const T &x) {
insert(size(), x);
}
T erase(int k) {
auto [a, bc] = split(root, k);
auto [b, c] = split(bc, 1);
T res = nodes[b].val;
recycle_node(b);
root = merge(a, c);
return res;
}
T pop_front() {
return erase(0);
}
T pop_back() {
return erase(size() - 1);
}
T get(int k) {
auto [a, bc] = split(root, k);
auto [b, c] = split(bc, 1);
T res = nodes[b].val;
root = merge(merge(a, b), c);
return res;
}
void set(int k, const T &x) {
auto [a, bc] = split(root, k);
auto [b, c] = split(bc, 1);
Node &node = nodes[b];
node.val = x;
node.sum = x;
node.rsum = x;
node.rev = false;
node.has_lazy = false;
pull(b);
root = merge(merge(a, b), c);
}
void apply(int l, int r, const L &x) {
auto [a, b, c] = split3(root, l, r);
apply_node(b, x);
root = merge(merge(a, b), c);
}
void reverse(int l, int r) {
auto [a, b, c] = split3(root, l, r);
toggle(b);
root = merge(merge(a, b), c);
}
T fold(int l, int r) {
auto [a, b, c] = split3(root, l, r);
T res = b == -1 ? M::e() : nodes[b].sum;
root = merge(merge(a, b), c);
return res;
}
private:
unsigned next_rand() {
rng_state ^= rng_state << 7;
rng_state ^= rng_state >> 9;
return static_cast<unsigned>(rng_state);
}
int new_node(const T &x) {
unsigned pri = next_rand();
if (!free_nodes.empty()) {
int idx = free_nodes.back();
free_nodes.pop_back();
nodes[idx] = Node(pri, x);
return idx;
}
nodes.emplace_back(pri, x);
return (int)nodes.size() - 1;
}
void recycle_node(int x) {
if (x != -1) free_nodes.push_back(x);
}
void build_linear(const vector<T> &v) {
if (v.empty()) return;
vector<int> ids(v.size());
for (int i = 0; i < (int)v.size(); ++i) ids[i] = new_node(v[i]);
vector<int> st;
st.reserve(v.size());
for (int cur : ids) {
int last = -1;
while (!st.empty() && nodes[st.back()].pri > nodes[cur].pri) {
last = st.back();
st.pop_back();
}
nodes[cur].l = last;
if (!st.empty()) nodes[st.back()].r = cur;
st.push_back(cur);
}
root = st.front();
vector<int> ord;
ord.reserve(v.size());
st.assign(1, root);
while (!st.empty()) {
int x = st.back();
st.pop_back();
ord.push_back(x);
if (nodes[x].l != -1) st.push_back(nodes[x].l);
if (nodes[x].r != -1) st.push_back(nodes[x].r);
}
for (int i = (int)ord.size() - 1; i >= 0; --i) pull(ord[i]);
}
void apply_node(int x, const L &lazy) {
if (x == -1) return;
Node &node = nodes[x];
node.val = M::g(node.val, lazy);
node.sum = M::g(node.sum, lazy);
node.rsum = M::g(node.rsum, lazy);
if (node.has_lazy) node.lazy = M::h(node.lazy, lazy);
else {
node.lazy = lazy;
node.has_lazy = true;
}
}
void toggle(int x) {
if (x == -1) return;
Node &node = nodes[x];
swap(node.l, node.r);
swap(node.sum, node.rsum);
node.rev ^= 1;
}
void push(int x) {
if (x == -1) return;
Node &node = nodes[x];
if (node.rev) {
toggle(node.l);
toggle(node.r);
node.rev = false;
}
if (node.has_lazy) {
apply_node(node.l, node.lazy);
apply_node(node.r, node.lazy);
node.has_lazy = false;
}
}
void pull(int x) {
Node &node = nodes[x];
node.sz = 1;
node.sum = node.val;
node.rsum = node.val;
if (node.l != -1) {
const Node &left = nodes[node.l];
node.sz += left.sz;
node.sum = M::f(left.sum, node.sum);
node.rsum = M::f(node.rsum, left.rsum);
}
if (node.r != -1) {
const Node &right = nodes[node.r];
node.sz += right.sz;
node.sum = M::f(node.sum, right.sum);
node.rsum = M::f(right.rsum, node.rsum);
}
}
int merge(int a, int b) {
if (a == -1 || b == -1) return a == -1 ? b : a;
if (nodes[a].pri < nodes[b].pri) {
push(a);
nodes[a].r = merge(nodes[a].r, b);
pull(a);
return a;
}
push(b);
nodes[b].l = merge(a, nodes[b].l);
pull(b);
return b;
}
pair<int, int> split(int x, int k) {
if (x == -1) return {-1, -1};
push(x);
int left_size = nodes[x].l == -1 ? 0 : nodes[nodes[x].l].sz;
if (k <= left_size) {
auto [a, b] = split(nodes[x].l, k);
nodes[x].l = b;
pull(x);
return {a, x};
}
auto [a, b] = split(nodes[x].r, k - left_size - 1);
nodes[x].r = a;
pull(x);
return {x, b};
}
tuple<int, int, int> split3(int x, int l, int r) {
auto [a, bc] = split(x, l);
auto [b, c] = split(bc, r - l);
return {a, b, c};
}
};
/**
* @brief Implicit Treap
*/
#line 21 "test/yosupo_dynamic_sequence_range_affine_range_sum.test.cpp"
struct AffineSumMonoid {
using T = array<mint, 2>;
using L = array<mint, 2>;
static T f(T a, T b) { return {a[0] + b[0], a[1] + b[1]}; }
static T g(T a, L b) { return {a[0] * b[0] + a[1] * b[1], a[1]}; }
static L h(L a, L b) { return {a[0] * b[0], a[1] * b[0] + b[1]}; }
static T e() { return {0, 0}; }
static L l() { return {1, 0}; }
};
int main() {
Scanner sc;
Printer pr;
int n, q;
sc.read(n, q);
vector<array<mint, 2>> init(n);
for (int i = 0; i < n; ++i) {
int a;
sc.read(a);
init[i] = {a, 1};
}
ImplicitTreap<AffineSumMonoid> tr(init);
tr.reserve(n + q);
while (q--) {
int t;
sc.read(t);
if (t == 0) {
int pos, x;
sc.read(pos, x);
tr.insert(pos, {x, 1});
} else if (t == 1) {
int pos;
sc.read(pos);
tr.erase(pos);
} else if (t == 2) {
int l, r;
sc.read(l, r);
tr.reverse(l, r);
} else if (t == 3) {
int l, r, b, c;
sc.read(l, r, b, c);
tr.apply(l, r, {b, c});
} else {
int l, r;
sc.read(l, r);
pr.println(tr.fold(l, r)[0].val);
}
}
return 0;
}