test/data_structure/queue_operate_all_composite.0.test.cpp

View this file on GitHub
Last update: 2025-01-19 15:28:01+08:00
Problem: https://judge.yosupo.jp/problem/queue_operate_all_composite

Depends on

Code

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

#include "modint.hpp"
#include "swag.hpp"
#include <array>
#include <iostream>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    using mint              = ModInt<998244353>;
    using LinearFunction    = std::array<mint, 2>;
    const LinearFunction Id = {0, 1};
    // L(R)
    auto composition = [](const LinearFunction &L, const LinearFunction &R) {
        return LinearFunction{L[0] + L[1] * R[0], L[1] * R[1]};
    };
    // R(L)
    auto composition2 = [&](const LinearFunction &L, const LinearFunction &R) {
        return composition(R, L);
    };
    SWAG<LinearFunction, decltype(composition2)> swag(composition2);
    int Q;
    std::cin >> Q;
    while (Q--) {
        int cmd;
        std::cin >> cmd;
        if (cmd == 0) {
            mint a, b;
            std::cin >> a >> b;
            swag.push_back({b, a});
        } else if (cmd == 1) {
            swag.pop_front();
        } else {
            mint x;
            std::cin >> x;
            std::cout << composition(swag.query().value_or(Id), {x, 0}).at(0) << '\n';
        }
    }
    return 0;
}

#line 1 "test/data_structure/queue_operate_all_composite.0.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/queue_operate_all_composite"

#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 "swag.hpp"

#include <cassert>
#include <cstddef>
#include <optional>
#include <stack>
#line 8 "swag.hpp"
#include <vector>

// see: https://www.hirzels.com/martin/papers/debs17-tutorial.pdf
// requires: Op(Op(A,B),C) = Op(A,Op(B,C))
template<typename Tp, typename Op,
         std::enable_if_t<std::is_invocable_r_v<Tp, Op, const Tp &, const Tp &>, int> = 0>
class SWAG {
public:
    Op F;
    std::stack<Tp, std::vector<Tp>> Front, Back;
    std::optional<Tp> Agg;

    explicit SWAG(Op F) : F(F) {}
    bool empty() const { return Front.empty() && Back.empty(); }
    std::size_t size() const { return Front.size() + Back.size(); }
    void push_back(const Tp &v) {
        Back.push(v);
        Agg.emplace(Agg ? F(*Agg, v) : v);
    }
    void pop_front() {
        assert(!empty());
        if (Front.empty()) {
            Front.push(Back.top());
            Back.pop();
            while (!Back.empty()) {
                Front.push(F(Back.top(), Front.top()));
                Back.pop();
            }
            Agg.reset();
        }
        Front.pop();
    }

    // returns F(...F(F(Q[0],Q[1]),Q[2]),...,Q[N-1])
    std::optional<Tp> query() const {
        if (empty()) return {};
        if (Front.empty()) return Agg;
        if (!Agg) return Front.top();
        return F(Front.top(), *Agg);
    }
};
#line 5 "test/data_structure/queue_operate_all_composite.0.test.cpp"
#include <array>
#line 7 "test/data_structure/queue_operate_all_composite.0.test.cpp"

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    using mint              = ModInt<998244353>;
    using LinearFunction    = std::array<mint, 2>;
    const LinearFunction Id = {0, 1};
    // L(R)
    auto composition = [](const LinearFunction &L, const LinearFunction &R) {
        return LinearFunction{L[0] + L[1] * R[0], L[1] * R[1]};
    };
    // R(L)
    auto composition2 = [&](const LinearFunction &L, const LinearFunction &R) {
        return composition(R, L);
    };
    SWAG<LinearFunction, decltype(composition2)> swag(composition2);
    int Q;
    std::cin >> Q;
    while (Q--) {
        int cmd;
        std::cin >> cmd;
        if (cmd == 0) {
            mint a, b;
            std::cin >> a >> b;
            swag.push_back({b, a});
        } else if (cmd == 1) {
            swag.pop_front();
        } else {
            mint x;
            std::cin >> x;
            std::cout << composition(swag.query().value_or(Id), {x, 0}).at(0) << '\n';
        }
    }
    return 0;
}