test/yosupo_queue_operate_all_composite.test.cpp

View this file on GitHub
Last update: 2023-04-05 23:10:22+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 "../template.hpp"

#include "../DataStructure/SlidingWindowAgregation.hpp"


signed main(){    
    auto swagfunc=[](pair<ll,ll> p1,pair<ll,ll> p2){
        return make_pair(p1.first*p2.first%998244353,(p2.first*p1.second%998244353+p2.second)%998244353);
    };

    SWAG<pair<ll,ll>> que(swagfunc,make_pair(1ll,0ll));

    int q;cin>>q;
    while(q--){
        int t;cin>>t;
        if(t==0){
            ll a,b;cin>>a>>b;
            que.push(make_pair(a,b));
        }else if(t==1){
            que.pop();
        }else{
            ll x;cin>>x;
            auto p=que.get();
            cout<<(p.first*x%998244353+p.second)%998244353<<endl;
        }
    }
    return 0;
}

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

#line 1 "template.hpp"
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) begin(x),end(x)
#define rep(i,n) for(int i=0;i<(n);i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define mod 1000000007
using ll=long long;
const int INF=1000000000;
const ll LINF=1001002003004005006ll;
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
// ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}

struct IOSetup{
    IOSetup(){
        cin.tie(0);
        ios::sync_with_stdio(0);
        cout<<fixed<<setprecision(12);
    }
} iosetup;
 
template<typename T>
ostream &operator<<(ostream &os,const vector<T>&v){
    for(int i=0;i<(int)v.size();i++) os<<v[i]<<(i+1==(int)v.size()?"":" ");
    return os;
}
template<typename T>
istream &operator>>(istream &is,vector<T>&v){
    for(T &x:v)is>>x;
    return is;
}

#line 4 "test/yosupo_queue_operate_all_composite.test.cpp"

#line 1 "DataStructure/SlidingWindowAgregation.hpp"
// Monoid Sliding-Window-AGregation
template<typename Monoid>
struct SWAG{
    using F=function<Monoid(Monoid,Monoid)>;
    const F f;
    const Monoid e;
    stack<pair<Monoid,Monoid>> fr,ba;
    SWAG(const F f,const Monoid &e):f(f),e(e){}
    Monoid get(){
        Monoid a=fr.empty()?e:fr.top().second;
        Monoid b=ba.empty()?e:ba.top().second;
        return f(a,b);
    }
    void push(Monoid x){
        if(ba.empty()) ba.push(make_pair(x,x));
        else ba.push(make_pair(x,f(ba.top().second,x)));
    }
    void pop(){
        if(empty()) return ;
        if(!fr.empty()) fr.pop();
        else{
            while(!ba.empty()){
                pair<Monoid,Monoid> p=ba.top();ba.pop();
                if(fr.empty()) fr.push(make_pair(p.first,p.first));
                else fr.push(make_pair(p.first,f(p.first,fr.top().second)));
            }
            fr.pop();
        }
    }
    size_t size(){
        return fr.size()+ba.size();
    }
    bool empty(){
        return size()==0;
    }
};
#line 6 "test/yosupo_queue_operate_all_composite.test.cpp"


signed main(){    
    auto swagfunc=[](pair<ll,ll> p1,pair<ll,ll> p2){
        return make_pair(p1.first*p2.first%998244353,(p2.first*p1.second%998244353+p2.second)%998244353);
    };

    SWAG<pair<ll,ll>> que(swagfunc,make_pair(1ll,0ll));

    int q;cin>>q;
    while(q--){
        int t;cin>>t;
        if(t==0){
            ll a,b;cin>>a>>b;
            que.push(make_pair(a,b));
        }else if(t==1){
            que.pop();
        }else{
            ll x;cin>>x;
            auto p=que.get();
            cout<<(p.first*x%998244353+p.second)%998244353<<endl;
        }
    }
    return 0;
}