This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub Harui-i/library
#define PROBLEM "https://judge.yosupo.jp/problem/queue_operate_all_composite" #include "template/template.hpp" #include "math/modint.hpp" #include "structure/slide-window-aggregation.hpp" #include "math/linear_function.hpp" using mint = modint998244353; using LF = LinearFunction<mint>; // f_r(f_l) LF op(LF lf, LF rf) { return rf.composite(lf); } LF e() { return LF::Mul_Identity(); } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); FoldableDeque<LF,op,e> fdq; int Q; cin >> Q; for(int i=0; i<Q; i++) { int op; cin >> op; if (op == 0) { int a,b; cin >> a >> b; fdq.push_back({mint(a), mint(b)}); } else if (op == 1) { fdq.pop_front(); } else if (op == 2) { int x; cin >> x; LF all_prod = fdq.all_prod(); cout << all_prod(x).val() << endl; } } return 0; }
#line 1 "test/verify/yosupo-queue-operate-all-composite.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/queue_operate_all_composite" #line 1 "template/template.hpp" #include <iostream> #include <cassert> using namespace std; using ll = long long; template<class T> inline bool chmax(T& a, const T& b) {if (a<b) {a=b; return true;} return false;} template<class T> inline bool chmin(T& a, const T& b) {if (b<a) {a=b; return true;} return false;} const int INTINF = 1000001000; const int INTMAX = 2147483647; const ll LLMAX = 9223372036854775807; const ll LLINF = 1000000000000000000; #line 1 "math/modint.hpp" #line 1 "math/external_gcd.hpp" #include <tuple> // g,x,y template<typename T> constexpr std::tuple<T, T, T> extendedGCD(T a, T b) { T x0 = 1, y0 = 0, x1 = 0, y1 = 1; while (b != 0) { T q = a / b; T r = a % b; a = b; b = r; T xTemp = x0 - q * x1; x0 = x1; x1 = xTemp; T yTemp = y0 - q * y1; y0 = y1; y1 = yTemp; } return {a, x0, y0}; } #line 5 "math/modint.hpp" template<int MOD> struct static_modint { int value; constexpr explicit static_modint() : value(0) {} constexpr static_modint(long long v) { value = int(((v % MOD) + MOD) % MOD); } constexpr static_modint& operator+=(const static_modint& other) { if ((value += other.value) >= MOD) value -= MOD; return *this; } constexpr static_modint& operator-=(const static_modint& other) { if ((value -= other.value) < 0) value += MOD; return *this; } constexpr static_modint& operator*=(const static_modint& other) { value = int((long long)value * other.value % MOD); return *this; } constexpr static_modint operator+(const static_modint& other) const { return static_modint(*this) += other; } constexpr static_modint operator-(const static_modint& other) const { return static_modint(*this) -= other; } constexpr static_modint operator*(const static_modint& other) const { return static_modint(*this) *= other; } constexpr static_modint pow(long long exp) const { static_modint base = *this, res = static_modint(1); while (exp > 0) { if (exp & 1) res *= base; base *= base; exp >>= 1; } return res; } constexpr static_modint inv() const { //return pow(MOD - 2); int g,x,y; tie(g,x,y) = extendedGCD(value, MOD); assert(g==1); if (x < 0) { x += MOD; } //cerr << g << " " << x << " " << y << " " << value << endl; //assert((((long)x*value)%MOD + MOD)%MOD == 1); return x; } constexpr static_modint& operator/=(const static_modint& other) { return *this *= other.inv(); } constexpr static_modint operator/(const static_modint& other) const { return static_modint(*this) /= other; } constexpr bool operator!=(const static_modint& other) const { return val() != other.val(); } constexpr bool operator==(const static_modint& other) const { return val() == other.val(); } int val() const { return this->value; } friend std::ostream& operator<<(std::ostream& os, const static_modint& mi) { return os << mi.value; } friend std::istream& operator>>(std::istream& is, static_modint& mi) { long long x; is >> x; mi = static_modint(x); return is; } }; template <int mod> using modint = static_modint<mod>; using modint998244353 = modint<998244353>; using modint1000000007 = modint<1000000007>; #line 1 "structure/slide-window-aggregation.hpp" #include <vector> #include <algorithm> template <class S, S (*op)(S, S), S (*e)()> struct FoldableDeque { struct Node { S val; S prod; }; std::vector<Node> front, back; FoldableDeque() : front(), back() {} size_t size() const { return front.size() + back.size(); } bool empty() const { return front.size() + back.size() == 0; } // nyaanさんのをパクっており void rebalance() { int n = front.size() + back.size(); int s0 = n / 2 + (front.empty() ? n % 2 : 0); // frontにs0個 // backにN - s0個入れる vector<Node> a{front}; std::reverse(begin(a), end(a)); std::copy(begin(back), end(back), back_inserter(a)); front.clear(), back.clear(); for (int i = s0 - 1; i >= 0; i--) push_front(a[i].val); for (int i = s0; i < n; i++) push_back(a[i].val); return; } S all_prod() const { if (front.empty() && back.empty() ) return e(); if (front.empty()) { return back.back().prod; } else if (back.empty()) { return front.back().prod; } else return op(front.back().prod, back.back().prod) ; } void push_back(const S& x) { if (back.empty()) { back.push_back({x, x}); } else { // 順序怪しいかも back.push_back({x, op(back.back().prod, x) }); } } void push_front(const S& x) { if (front.empty()) { front.push_back({x, x}); } else { // 順序怪しいかも front.push_back({x, op(x, front.back().prod) }); } } void pop_back() { assert(size() > 0); if (back.empty()) rebalance(); back.pop_back(); } void pop_front() { assert(size() > 0); if (front.empty()) rebalance(); front.pop_back(); } }; #line 1 "math/linear_function.hpp" template <typename T> struct LinearFunction { T a, b; LinearFunction() : a{0}, b(0) {} LinearFunction(T _a, T _b) : a(_a), b(_b) {} static LinearFunction Add_Identity() { return LinearFunction(T(0), T(0)); } static LinearFunction Mul_Identity(){ return LinearFunction(T(1), T(0)); } // f(g()) LinearFunction composite(LinearFunction& g) const { return LinearFunction(a * g.a, a * g.b + b); } LinearFunction operator+(const LinearFunction& rhs) const { return LinearFunction(a + rhs.a, b + rhs.b); } // rhs(f()) LinearFunction operator*(const LinearFunction& rhs) const { LinearFunction f = *this; return rhs.composite(f); } T operator()(T x) const { return a * x + b; } }; #line 7 "test/verify/yosupo-queue-operate-all-composite.test.cpp" using mint = modint998244353; using LF = LinearFunction<mint>; // f_r(f_l) LF op(LF lf, LF rf) { return rf.composite(lf); } LF e() { return LF::Mul_Identity(); } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); FoldableDeque<LF,op,e> fdq; int Q; cin >> Q; for(int i=0; i<Q; i++) { int op; cin >> op; if (op == 0) { int a,b; cin >> a >> b; fdq.push_back({mint(a), mint(b)}); } else if (op == 1) { fdq.pop_front(); } else if (op == 2) { int x; cin >> x; LF all_prod = fdq.all_prod(); cout << all_prod(x).val() << endl; } } return 0; }