hly1204's library
This documentation is automatically generated by online-judge-tools/verification-helper
test/data_structure/dynamic_sequence_range_affine_range_sum.0.test.cpp
- View this file on GitHub
- Last update: 2025-01-19 15:28:01+08:00
- Problem: https://judge.yosupo.jp/problem/dynamic_sequence_range_affine_range_sum
Depends on
Code
#define PROBLEM "https://judge.yosupo.jp/problem/dynamic_sequence_range_affine_range_sum"
#include "modint.hpp"
#include "treap_node_base.hpp"
#include <iostream>
#include <memory>
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
using mint = ModInt<998244353>;
struct TreapNode : TreapNodeBase<TreapNode> {
mint Val, Sum, Add, Mul = {1};
void do_propagate() {
if (left()) {
left()->Add = Mul * left()->Add + Add;
left()->Mul *= Mul;
left()->Sum = Add * left()->size() + Mul * left()->Sum;
}
if (right()) {
right()->Add = Mul * right()->Add + Add;
right()->Mul *= Mul;
right()->Sum = Add * right()->size() + Mul * right()->Sum;
}
Val = Add + Mul * Val;
Add = 0;
Mul = 1;
}
void do_update() {
Sum = Val;
if (left()) Sum += left()->Sum;
if (right()) Sum += right()->Sum;
}
};
int n, q;
std::cin >> n >> q;
auto buf = std::make_unique<TreapNode[]>(n + q);
TreapNode *root = nullptr;
for (int i = 0; i < n; ++i) {
std::cin >> buf[i].Val;
root = TreapNode::join(root, &buf[i]);
}
for (int i = 0; i < q; ++i) {
int cmd;
std::cin >> cmd;
switch (cmd) {
case 0: {
int pos;
std::cin >> pos >> buf[n + i].Val;
auto [R0, R1] = TreapNode::split(root, pos);
root = TreapNode::join(R0, &buf[n + i], R1);
break;
}
case 1: {
int pos;
std::cin >> pos;
auto [R0, R1, R2] = TreapNode::split(root, pos, 1);
root = TreapNode::join(R0, R2);
break;
}
case 2: {
int l, r;
std::cin >> l >> r;
auto [R0, R1, R2] = TreapNode::split(root, l, r - l);
R1->flip();
root = TreapNode::join(R0, R1, R2);
break;
}
case 3: {
int l, r;
std::cin >> l >> r;
auto [R0, R1, R2] = TreapNode::split(root, l, r - l);
std::cin >> R1->Mul >> R1->Add;
root = TreapNode::join(R0, R1, R2);
break;
}
case 4: {
int l, r;
std::cin >> l >> r;
auto [R0, R1, R2] = TreapNode::split(root, l, r - l);
std::cout << R1->Sum << '\n';
root = TreapNode::join(R0, R1, R2);
break;
}
default: break;
}
}
return 0;
}#line 1 "test/data_structure/dynamic_sequence_range_affine_range_sum.0.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/dynamic_sequence_range_affine_range_sum"
#line 2 "modint.hpp"
#include <iostream>
#include <type_traits>
// clang-format off
template<unsigned Mod> class ModInt {
static_assert((Mod >> 31) == 0, "`Mod` must less than 2^(31)");
template<typename Int>
static std::enable_if_t<std::is_integral_v<Int>, unsigned> safe_mod(Int v) { using D = std::common_type_t<Int, unsigned>; return (v %= (int)Mod) < 0 ? (D)(v + (int)Mod) : (D)v; }
struct PrivateConstructor {} static inline private_constructor{};
ModInt(PrivateConstructor, unsigned v) : v_(v) {}
unsigned v_;
public:
static unsigned mod() { return Mod; }
static ModInt from_raw(unsigned v) { return ModInt(private_constructor, v); }
static ModInt zero() { return from_raw(0); }
static ModInt one() { return from_raw(1); }
bool is_zero() const { return v_ == 0; }
bool is_one() const { return v_ == 1; }
ModInt() : v_() {}
template<typename Int, typename std::enable_if_t<std::is_signed_v<Int>, int> = 0> ModInt(Int v) : v_(safe_mod(v)) {}
template<typename Int, typename std::enable_if_t<std::is_unsigned_v<Int>, int> = 0> ModInt(Int v) : v_(v % Mod) {}
unsigned val() const { return v_; }
ModInt operator-() const { return from_raw(v_ == 0 ? v_ : Mod - v_); }
ModInt pow(long long e) const { if (e < 0) return inv().pow(-e); for (ModInt x(*this), res(from_raw(1));; x *= x) { if (e & 1) res *= x; if ((e >>= 1) == 0) return res; }}
ModInt inv() const { int x1 = 1, x3 = 0, a = val(), b = Mod; while (b) { const int q = a / b, x1_old = x1, a_old = a; x1 = x3, x3 = x1_old - x3 * q, a = b, b = a_old - b * q; } return from_raw(x1 < 0 ? x1 + (int)Mod : x1); }
template<bool Odd = (Mod & 1)> std::enable_if_t<Odd, ModInt> div_by_2() const { if (v_ & 1) return from_raw((v_ + Mod) >> 1); return from_raw(v_ >> 1); }
ModInt &operator+=(const ModInt &a) { if ((v_ += a.v_) >= Mod) v_ -= Mod; return *this; }
ModInt &operator-=(const ModInt &a) { if ((v_ += Mod - a.v_) >= Mod) v_ -= Mod; return *this; }
ModInt &operator*=(const ModInt &a) { v_ = (unsigned long long)v_ * a.v_ % Mod; return *this; }
ModInt &operator/=(const ModInt &a) { return *this *= a.inv(); }
ModInt &operator++() { return *this += one(); }
ModInt operator++(int) { ModInt o(*this); *this += one(); return o; }
ModInt &operator--() { return *this -= one(); }
ModInt operator--(int) { ModInt o(*this); *this -= one(); return o; }
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.v_ == b.v_; }
friend bool operator!=(const ModInt &a, const ModInt &b) { return a.v_ != b.v_; }
friend std::istream &operator>>(std::istream &a, ModInt &b) { int v; a >> v; b.v_ = safe_mod(v); return a; }
friend std::ostream &operator<<(std::ostream &a, const ModInt &b) { return a << b.val(); }
};
// clang-format on
#line 2 "treap_node_base.hpp"
#line 2 "rng.hpp"
#include <cstdint>
#include <limits>
// see: https://prng.di.unimi.it/xoshiro256starstar.c
// original license CC0 1.0
class xoshiro256starstar {
using u64 = std::uint64_t;
static inline u64 rotl(const u64 x, int k) { return (x << k) | (x >> (64 - k)); }
u64 s_[4];
u64 next() {
const u64 res = rotl(s_[1] * 5, 7) * 9;
const u64 t = s_[1] << 17;
s_[2] ^= s_[0];
s_[3] ^= s_[1];
s_[1] ^= s_[2];
s_[0] ^= s_[3];
s_[2] ^= t;
s_[3] = rotl(s_[3], 45);
return res;
}
public:
// see: https://prng.di.unimi.it/splitmix64.c
// original license CC0 1.0
explicit xoshiro256starstar(u64 seed) {
for (int i = 0; i < 4; ++i) {
u64 z = (seed += 0x9e3779b97f4a7c15);
z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
s_[i] = z ^ (z >> 31);
}
}
// see: https://en.cppreference.com/w/cpp/named_req/UniformRandomBitGenerator
using result_type = u64;
static constexpr u64 min() { return std::numeric_limits<u64>::min(); }
static constexpr u64 max() { return std::numeric_limits<u64>::max(); }
u64 operator()() { return next(); }
};
#line 4 "treap_node_base.hpp"
#include <array>
#include <random>
#include <utility>
template<typename TreapNode> class TreapNodeBase {
TreapNodeBase *L;
TreapNodeBase *R;
int Rank;
int Size;
bool NeedFlip;
static inline xoshiro256starstar gen{std::random_device{}()};
static inline std::uniform_int_distribution<int> dis{0, 998244353};
TreapNode *derived() { return (TreapNode *)this; }
// CRTP reimplement
void do_flip() {}
void do_propagate() {}
void do_update() {}
protected:
void base_flip() {
NeedFlip = !NeedFlip;
std::swap(L, R);
derived()->do_flip();
}
// base_propagate() is called to propagate the update information to child(ren).
// There is no need to update the information combined from child(ren)
// which should be done in base_update().
void base_propagate() {
derived()->do_propagate();
if (NeedFlip) {
NeedFlip = false;
if (L) L->base_flip();
if (R) R->base_flip();
}
}
// base_update() is called to update the information combined from child(ren).
void base_update() {
Size = 1;
if (L) Size += L->Size;
if (R) Size += R->Size;
derived()->do_update();
}
static TreapNodeBase *base_join(TreapNodeBase *a, TreapNodeBase *b) {
if (a == nullptr) {
if (b) b->base_propagate(), b->base_update();
return b;
}
if (b == nullptr) {
if (a) a->base_propagate(), a->base_update();
return a;
}
a->base_propagate();
b->base_propagate();
if (a->Rank < b->Rank) {
b->L = base_join(a, b->L);
b->base_update();
return b;
}
a->R = base_join(a->R, b);
a->base_update();
return a;
}
static std::array<TreapNodeBase *, 2> base_split(TreapNodeBase *a, int k) {
if (a == nullptr) return {nullptr, nullptr};
a->base_propagate();
if (k == 0) return {nullptr, a};
if (k == a->Size) return {a, nullptr};
const int leftsize = a->L != nullptr ? a->L->Size : 0;
if (leftsize < k) {
auto [b, c] = base_split(a->R, k - leftsize - 1);
a->R = b;
a->base_update();
return {a, c};
}
auto [b, c] = base_split(a->L, k);
a->L = c;
a->base_update();
return {b, a};
}
TreapNodeBase() : L(), R(), Rank(dis(gen)), Size(1), NeedFlip() {}
public:
int size() const { return Size; }
int rank() const { return Rank; }
TreapNode *left() const { return (TreapNode *)L; }
TreapNode *right() const { return (TreapNode *)R; }
void flip() { base_flip(); }
template<typename... Nodes> static TreapNode *join(Nodes... node) {
struct Helper {
TreapNodeBase *Val;
Helper &operator|(TreapNodeBase *A) {
Val = TreapNodeBase::base_join(Val, A);
return *this;
}
} nil{nullptr};
return (TreapNode *)(nil | ... | node).Val;
}
template<typename... Parts>
static std::array<TreapNode *, sizeof...(Parts) + 1> split(TreapNode *a, Parts... part) {
std::array<TreapNode *, sizeof...(Parts) + 1> res;
res[0] = a;
int index = 0;
(
[&](int s) {
auto [l, r] = base_split(res[index], s);
res[index] = (TreapNode *)l;
res[++index] = (TreapNode *)r;
}(part),
...);
return res;
}
TreapNode *select(int k) {
base_propagate();
const int leftsize = left() ? left()->size() : 0;
if (k == leftsize) return (TreapNode *)this;
if (k < leftsize) return left()->select(k);
return right()->select(k - leftsize - 1);
}
};
#line 6 "test/data_structure/dynamic_sequence_range_affine_range_sum.0.test.cpp"
#include <memory>
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
using mint = ModInt<998244353>;
struct TreapNode : TreapNodeBase<TreapNode> {
mint Val, Sum, Add, Mul = {1};
void do_propagate() {
if (left()) {
left()->Add = Mul * left()->Add + Add;
left()->Mul *= Mul;
left()->Sum = Add * left()->size() + Mul * left()->Sum;
}
if (right()) {
right()->Add = Mul * right()->Add + Add;
right()->Mul *= Mul;
right()->Sum = Add * right()->size() + Mul * right()->Sum;
}
Val = Add + Mul * Val;
Add = 0;
Mul = 1;
}
void do_update() {
Sum = Val;
if (left()) Sum += left()->Sum;
if (right()) Sum += right()->Sum;
}
};
int n, q;
std::cin >> n >> q;
auto buf = std::make_unique<TreapNode[]>(n + q);
TreapNode *root = nullptr;
for (int i = 0; i < n; ++i) {
std::cin >> buf[i].Val;
root = TreapNode::join(root, &buf[i]);
}
for (int i = 0; i < q; ++i) {
int cmd;
std::cin >> cmd;
switch (cmd) {
case 0: {
int pos;
std::cin >> pos >> buf[n + i].Val;
auto [R0, R1] = TreapNode::split(root, pos);
root = TreapNode::join(R0, &buf[n + i], R1);
break;
}
case 1: {
int pos;
std::cin >> pos;
auto [R0, R1, R2] = TreapNode::split(root, pos, 1);
root = TreapNode::join(R0, R2);
break;
}
case 2: {
int l, r;
std::cin >> l >> r;
auto [R0, R1, R2] = TreapNode::split(root, l, r - l);
R1->flip();
root = TreapNode::join(R0, R1, R2);
break;
}
case 3: {
int l, r;
std::cin >> l >> r;
auto [R0, R1, R2] = TreapNode::split(root, l, r - l);
std::cin >> R1->Mul >> R1->Add;
root = TreapNode::join(R0, R1, R2);
break;
}
case 4: {
int l, r;
std::cin >> l >> r;
auto [R0, R1, R2] = TreapNode::split(root, l, r - l);
std::cout << R1->Sum << '\n';
root = TreapNode::join(R0, R1, R2);
break;
}
default: break;
}
}
return 0;
}