test/yosupo/ds/deque_operate_all_composite.test.cpp

View this file on GitHub
Last update: 2025-09-20 17:47:50+07:00
Problem: https://judge.yosupo.jp/problem/deque_operate_all_composite

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/deque_operate_all_composite"

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

#include "ds/deque_aggregation.hpp"
#include "math/modint.hpp"

using mint = modint998;

struct M {
    struct T {
        mint a = 1, b = 0;
        mint operator()(mint x) { return a * x + b; }
    };
    static T id() { return {}; }
    static T op(T l, T r) { return {r.a * l.a, r.a * l.b + r.b}; }
};

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int q;
    cin >> q;
    DequeAggregation<M> dq;
    while (q--) {
        int op, a, b, x;
        cin >> op;
        if (op == 0 || op == 1) {
            cin >> a >> b;
            op == 0 ? dq.push_front({a, b}) : dq.push_back({a, b});
        } else if (op == 2 || op == 3) {
            op == 2 ? dq.pop_front() : dq.pop_back();
        } else {
            cin >> x;
            cout << dq.query()(x) << "\n";
        }
    }
}

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

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

#line 2 "ds/deque_aggregation.hpp"

template<class M> struct DequeAggregation {
    using T = typename M::T;

    T front() const { return f.size() ? getf() : b.front()[0]; }
    T back() const { return b.size() ? getb() : f.back()[0]; }
    void push_front(const T &x) { f.push_back({x, M::op(x, getf<1>())}); }
    void push_back(const T &x) { b.push_back({x, M::op(getb<1>(), x)}); }
    void pop_front() {
        assert(size());
        if (f.empty()) rebalance();
        f.pop_back();
    }
    void pop_back() {
        assert(size());
        if (b.empty()) rebalance();
        b.pop_back();
    }

    T query() const { return M::op(getf<1>(), getb<1>()); }

    int size() const { return int(f.size() + b.size()); }
    bool empty() const { return size() == 0; }

    vector<array<T, 2>> f, b;

  private:
    template<int d = 0> T getf() const {
        return f.size() ? f.back()[d] : M::id();
    }
    template<int d = 0> T getb() const {
        return b.size() ? b.back()[d] : M::id();
    }
    void rebalance() {
        bool ef = f.empty();
        int n = size(), i = 0, m = n / 2 + ef;
        vector<T> xs(n);
        for (; f.size(); f.pop_back()) xs[i++] = getf();
        for (; b.size(); b.pop_back()) xs[i++] = getb();
        if (ef) reverse(begin(xs), end(xs));
        for (i = m - 1; i >= 0; i--) push_front(xs[i]);
        for (i = m; i < n; i++) push_back(xs[i]);
    }
};
#line 2 "math/modint.hpp"

// clang-format off
template<uint32_t m> struct modint {
    static_assert(m >= 1, "Modulus must be in the range [1;2^31)");

    using mint = modint;
    static constexpr bool is_simple = true;

    static constexpr uint32_t mod() noexcept { return m; }
    constexpr modint() noexcept = default;
    constexpr modint(int64_t v) noexcept : _v(uint32_t((v %= m) < 0 ? v + m : v)) {}
    constexpr static mint raw(uint32_t v) noexcept { mint x; return x._v = v, x; }
    template<class T> constexpr explicit operator T() const noexcept { return _v; }

    constexpr mint &operator++() noexcept { return _v = ++_v == mod() ? 0 : _v, *this; }
    constexpr mint &operator--() noexcept { --(_v ? _v : _v = mod()); return *this; }
    constexpr mint operator++(int) noexcept { return exchange(*this, ++mint(*this)); }
    constexpr mint operator--(int) noexcept { return exchange(*this, --mint(*this)); }

    constexpr mint &operator+=(mint rhs) noexcept {
        return _v = int(_v += rhs._v - mod()) < 0 ? _v + mod() : _v, *this;
    }
    constexpr mint &operator-=(mint rhs) noexcept {
        return _v = int(_v -= rhs._v) < 0 ? _v + mod() : _v, *this;
    }
    constexpr mint &operator*=(mint rhs) noexcept {
        return _v = uint64_t(_v) * rhs._v % mod(), *this;
    }
    constexpr mint &operator/=(mint rhs) noexcept {
        return *this = *this * rhs.inv();
    }

    constexpr friend mint operator+(mint l, mint r) noexcept { return l += r; }
    constexpr friend mint operator-(mint l, mint r) noexcept { return l -= r; }
    constexpr friend mint operator*(mint l, mint r) noexcept { return l *= r; }
    constexpr friend mint operator/(mint l, mint r) noexcept { return l /= r; }

    constexpr mint operator+() const noexcept { return *this; }
    constexpr mint operator-() const noexcept { return raw(_v ? mod() - _v : 0); }

    constexpr friend bool operator==(mint l, mint r) noexcept { return l._v == r._v; }
    constexpr friend bool operator!=(mint l, mint r) noexcept { return l._v != r._v; }
    constexpr friend bool operator<(mint l, mint r) noexcept { return l._v < r._v; }

    constexpr mint pow(uint64_t n) const noexcept {
        mint b = *this, res = 1;
        while (n) n & 1 ? res *= b : 0, b *= b, n >>= 1;
        return res;
    }

    constexpr mint inv() const noexcept {
        int a = _v, b = mod(), x = 1, y = 0;
        while (b) {
            x = exchange(y, x - a / b * y);
            a = exchange(b, a % b);
        }
        assert(a == 1);
        return x;
    }

    friend istream &operator>>(istream &is, mint &x) {
        int64_t v{};
        return is >> v, x = v, is;
    }
    friend ostream &operator<<(ostream &os, const mint &x) { return os << x._v; }

  private:
    uint32_t _v = 0;
};
using modint107 = modint<1'000'000'007>;
using modint998 = modint<998'244'353>;
// clang-format on
#line 8 "test/yosupo/ds/deque_operate_all_composite.test.cpp"

using mint = modint998;

struct M {
    struct T {
        mint a = 1, b = 0;
        mint operator()(mint x) { return a * x + b; }
    };
    static T id() { return {}; }
    static T op(T l, T r) { return {r.a * l.a, r.a * l.b + r.b}; }
};

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int q;
    cin >> q;
    DequeAggregation<M> dq;
    while (q--) {
        int op, a, b, x;
        cin >> op;
        if (op == 0 || op == 1) {
            cin >> a >> b;
            op == 0 ? dq.push_front({a, b}) : dq.push_back({a, b});
        } else if (op == 2 || op == 3) {
            op == 2 ? dq.pop_front() : dq.pop_back();
        } else {
            cin >> x;
            cout << dq.query()(x) << "\n";
        }
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	5 ms	4 MB
g++	example_01	AC	4 ms	4 MB
g++	large_max_00	AC	81 ms	7 MB
g++	large_max_01	AC	83 ms	7 MB
g++	large_min_00	AC	73 ms	4 MB
g++	large_min_01	AC	73 ms	4 MB
g++	large_triangle_00	AC	74 ms	5 MB
g++	large_triangle_01	AC	70 ms	5 MB
g++	max_random_00	AC	95 ms	11 MB
g++	max_random_01	AC	95 ms	11 MB
g++	max_random_02	AC	94 ms	12 MB
g++	random_00	AC	60 ms	5 MB
g++	random_01	AC	70 ms	5 MB
g++	random_02	AC	12 ms	4 MB
g++	small_00	AC	4 ms	4 MB
g++	small_01	AC	4 ms	4 MB
clang++	example_00	AC	5 ms	4 MB
clang++	example_01	AC	4 ms	4 MB
clang++	large_max_00	AC	82 ms	7 MB
clang++	large_max_01	AC	82 ms	7 MB
clang++	large_min_00	AC	72 ms	4 MB
clang++	large_min_01	AC	71 ms	4 MB
clang++	large_triangle_00	AC	70 ms	5 MB
clang++	large_triangle_01	AC	66 ms	5 MB
clang++	max_random_00	AC	93 ms	11 MB
clang++	max_random_01	AC	95 ms	12 MB
clang++	max_random_02	AC	93 ms	12 MB
clang++	random_00	AC	60 ms	5 MB
clang++	random_01	AC	74 ms	5 MB
clang++	random_02	AC	12 ms	4 MB
clang++	small_00	AC	4 ms	4 MB
clang++	small_01	AC	4 ms	4 MB