Test/yosupo-judge/SlidingWindowAggregation.test.cpp

View this file on GitHub
Last update: 2021-09-20 19:48:28+09: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<bits/stdc++.h>
using namespace std;

#include"../../Other/Template.cpp"
#include"../../DataStructure/SlidingWindowAggregation.cpp"

constexpr long long MOD = 998244353;

using S = pair<long long,long long>;

S op(S A,S B) {
    return {A.first * B.first % MOD,(B.first * A.second + B.second) % MOD};
}

int main() {
    int Q;
    cin >> Q;
    SWAG<S> swag(op);
    for(int i = 0;i < Q;i++) {
        int q;
        cin >> q;
        if(q == 0) {
            long long a,b;
            cin >> a >> b;
            swag.push({a,b});
        }
        else if(q == 1) {
            swag.pop();
        }
        else {
            long long x;
            cin >> x;
            if(swag.empty()) cout << x << endl;
            else {
                S res = swag.fold_all();
                cout << (res.first * x + res.second) % MOD << endl;
            }
        }
    }
}

#line 1 "Test/yosupo-judge/SlidingWindowAggregation.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/queue_operate_all_composite"

#include<bits/stdc++.h>
using namespace std;

#line 1 "Other/Template.cpp"
constexpr int Inf = 2000000030;
constexpr long long INF= 2000000000000000000;

template<typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
#line 1 "DataStructure/SlidingWindowAggregation.cpp"
template<class T>
class SWAG {
    class Node {
    public:
        T val,sum;
        Node(const T& val,const T& sum) : val(val),sum(sum) {}
    };

    std::stack<Node> front_stack,back_stack;
    function<T(T,T)> op;

public:
    SWAG(const function<T(T,T)> op) : op(op) {}

    bool empty() {
        return front_stack.empty() && back_stack.empty();
    }

    T fold_all() {
        assert(!empty());
        if(front_stack.empty()) {
            return back_stack.top().sum;
        }
        else if(back_stack.empty()) {
            return front_stack.top().sum;
        }
        else {
            return op(front_stack.top().sum,back_stack.top().sum);
        }
    }

    void push(T x) {
        if(back_stack.empty()) back_stack.emplace(x,x);
        else back_stack.emplace(x,op(back_stack.top().sum,x));
    }

    void pop() {
        assert(!empty());
        if(front_stack.empty()) {
            front_stack.emplace(back_stack.top().val,back_stack.top().val);
            back_stack.pop();
            while(!back_stack.empty()) {
                T tmp{op(back_stack.top().val,front_stack.top().sum)};
                front_stack.emplace(back_stack.top().val,tmp);
                back_stack.pop();
            }
        }
        front_stack.pop();
    }
};
#line 8 "Test/yosupo-judge/SlidingWindowAggregation.test.cpp"

constexpr long long MOD = 998244353;

using S = pair<long long,long long>;

S op(S A,S B) {
    return {A.first * B.first % MOD,(B.first * A.second + B.second) % MOD};
}

int main() {
    int Q;
    cin >> Q;
    SWAG<S> swag(op);
    for(int i = 0;i < Q;i++) {
        int q;
        cin >> q;
        if(q == 0) {
            long long a,b;
            cin >> a >> b;
            swag.push({a,b});
        }
        else if(q == 1) {
            swag.pop();
        }
        else {
            long long x;
            cin >> x;
            if(swag.empty()) cout << x << endl;
            else {
                S res = swag.fold_all();
                cout << (res.first * x + res.second) % MOD << endl;
            }
        }
    }
}