library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub Harui-i/library

:heavy_check_mark: test/verify/yosupo-queue-operate-all-composite.test.cpp

Depends on

Code

#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"
#include <type_traits>
#line 7 "math/modint.hpp"

template<int MOD, typename T = int>
struct static_modint {
    T value;

    constexpr explicit static_modint() : value(0) {}

    constexpr static_modint(long long v) {
        if constexpr (std::is_same<T, double>::value) {
            value = double(v);
        }
        else {
            value = int(((v % MOD) + MOD) % MOD);
        }
    }

    constexpr static_modint& operator+=(const static_modint& other) {
        if constexpr (std::is_same<T, double>::value) {
            value += other.value;
        }
        else {
            if ((value += other.value) >= MOD) value -= MOD;
        }
        return *this;
    }

    constexpr static_modint& operator-=(const static_modint& other) {
        if constexpr (std::is_same<T, double>::value) {
            value -= other.value;
        }
        else {
            if ((value -= other.value) < 0) value += MOD;
        }
        return *this;
    }

    constexpr static_modint& operator*=(const static_modint& other) {
        if constexpr (std::is_same<T, double>::value) {
            value *= other.value;
        }
        else {
            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 {
        if constexpr (std::is_same<T, double>::value) {
            static_modint ret;
            ret.value = double(1.0) / value;
            return ret;
        }
        else {
            int g, x, y;
            std::tie(g, x, y) = extendedGCD(value, MOD);
            assert(g == 1);
            if (x < 0) x += MOD;
            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();
    }

    T val() const {
        if constexpr (std::is_same<T, double>::value) {
            return double(value);
        }
        else 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 doublemodint = static_modint<59, double>;
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;
}
Back to top page