This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub SSRS-cp/cp_library
#define PROBLEM "https://judge.yosupo.jp/problem/queue_operate_all_composite" #include <bits/stdc++.h> using namespace std; const long long MOD = 998244353; #include "../../../data_structure/other/sliding_window_aggregation.hpp" #include "../../../other/monoids/linear.hpp" int main(){ int Q; cin >> Q; sliding_window_aggregation<linear> S(composite, linear()); for (int i = 0; i < Q; i++){ int t; cin >> t; if (t == 0){ int a, b; cin >> a >> b; S.push(linear(a, b)); } if (t == 1){ S.pop(); } if (t == 2){ int x; cin >> x; cout << value(S.get(),x) << endl; } } }
#line 1 "test/library_checker/data_structure/queue_operate_all_composite.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/queue_operate_all_composite" #include <bits/stdc++.h> using namespace std; const long long MOD = 998244353; #line 2 "data_structure/other/sliding_window_aggregation.hpp" /** * @brief Sliding Window Aggregation */ template <typename T> struct sliding_window_aggregation{ function<T(T, T)> f; T E; stack<pair<T, T>> fr, bk; sliding_window_aggregation(function<T(T, T)> f, T E): f(f), E(E){ } void push(T x){ if (fr.empty()){ fr.push(make_pair(x, x)); } else { fr.push(make_pair(x, f(fr.top().second, x))); } } void pop(){ if (bk.empty()){ while (!fr.empty()){ T x = fr.top().first; fr.pop(); if (bk.empty()){ bk.push(make_pair(x, x)); } else { bk.push(make_pair(x, f(x, bk.top().second))); } } } bk.pop(); } T get(){ T ans1 = E; if (!fr.empty()){ ans1 = fr.top().second; } T ans2 = E; if (!bk.empty()){ ans2 = bk.top().second; } return f(ans2, ans1); } }; #line 2 "other/monoids/linear.hpp" struct linear{ long long a, b; linear(){ a = 1; b = 0; } linear(int a, int b): a(a), b(b){ } }; linear composite(linear A, linear B){ return linear(A.a * B.a % MOD, (A.b * B.a + B.b) % MOD); } int value(linear A, int x){ return (A.a * x + A.b) % MOD; } #line 7 "test/library_checker/data_structure/queue_operate_all_composite.test.cpp" int main(){ int Q; cin >> Q; sliding_window_aggregation<linear> S(composite, linear()); for (int i = 0; i < Q; i++){ int t; cin >> t; if (t == 0){ int a, b; cin >> a >> b; S.push(linear(a, b)); } if (t == 1){ S.pop(); } if (t == 2){ int x; cin >> x; cout << value(S.get(),x) << endl; } } }