区間 \([L,R)\) に対して、\(v=x\) で入ったときの最終的な \(v\) の値を \(f _ {[L,R)}(x)\) と定めます。

すると、\(f _ {[L,R)}(x)\) はいくつかの一次関数 \(ax+b\) の最大値として表すことができます。

これを適切に管理することでもこの問題を解くことができます。 具体的には、\(0\leq x\leq 10 ^ {18}\) かつ \(0\leq f _ {[L,R)}(x)\leq 10 ^ {18}\) において最大値をとりうる一次関数だけを管理すると、どの区間 \([L,R)\) に対してもたかだか \(\lceil\log _ 210 ^ {18}\rceil\) 個の一次関数を管理すればよいことになります。

あとは、関数の合成 \(f _ {[L,R)}(x)=f _ {[M,R)}\circ f _ {[L,M)}(x)\) を高速に計算できればよいです。 これは、一次関数を \(a\) の昇順で持っておくことで \(O(\)一次関数の個数の合計\()\) 時間で合成が計算できます。

詳細な実装は以下の実装例を参考にしてください。

#include <iostream>
#include <algorithm>
#include <vector>
#include <ranges>
#include <atcoder/segtree>

int main() {
    using namespace std;
    // 一次関数の max の inf 未満の部分を管理する
    constexpr unsigned long inf = 1000000000000000000;
    class piecewise_linear_convex {
        // 一次関数
        struct linear {
            unsigned long a, b;

            constexpr unsigned long operator()(unsigned long x) const {
                if ((inf - b) / a < x)
                    return inf;
                return x * a + b;
            }
        };

        vector<pair<unsigned long, linear>> piece;
    public:
        [[nodiscard]] constexpr piecewise_linear_convex() : piece{{0, {1, 0}}} {}

        [[nodiscard]] constexpr explicit piecewise_linear_convex(vector<pair<unsigned long, linear>> &&_p) : piece{std::move(_p)} {}

        [[nodiscard]] constexpr explicit piecewise_linear_convex(const vector<pair<unsigned long, linear>> &_p) : piece{_p} {}

        // 代入したときの値を求める
        constexpr unsigned long operator()(unsigned long x) const {
            if (empty(piece))
                return inf;
            return prev(ranges::upper_bound(piece, x, less<>{}, &pair<unsigned long, linear>::first))->second(x);
        }

        // (A, B) の単一要素に対する値
        static constexpr piecewise_linear_convex from_single_state(unsigned long a, unsigned long b) {
            if (b == 1)
                return piecewise_linear_convex{{{0, {1, a}}}};
            return piecewise_linear_convex{{{0, {1, a}}, {(a + b - 1) / (b - 1), {b, 0}}}};
        }

        // 関数 [L, M) と [M, R) の合成
        constexpr piecewise_linear_convex operator+(const piecewise_linear_convex &rhs) const {
            const auto &p_lhs{this->piece};
            const auto &p_rhs{rhs.piece};
            // 0 を入れたときに inf になるなら空を返す
            if (empty(p_lhs) || rhs(p_lhs.front().second(0)) == inf)
                return piecewise_linear_convex{{}};

            const auto &N_lhs{size(p_lhs)}, &N_rhs{size(p_rhs)};
            vector<pair<unsigned long, linear>> result;
            // 値 x を代入したときに最大値をとる一次関数の index を求める
            const auto find_bound{[](const auto &seq, unsigned long key, unsigned start) -> unsigned {
                const auto N{size(seq)};
                for (unsigned i{start}; i < N; ++i)
                    if (seq[i].first > key)
                        return i;
                return N;
            }};
            // 結果に一次関数を追加する（最大値を取る区間の昇順に追加する）
            auto add_line{[prev_x{inf}](auto &&seq, unsigned long begin, linear func) mutable {
                if (prev_x == begin)
                    seq.back().second = func;
                else
                    seq.emplace_back(begin, func);
                prev_x = begin;
            }};

            for (unsigned i_lhs{}, i_rhs{find_bound(p_rhs, p_lhs[i_lhs].second(p_lhs[i_lhs].first), 0)}; i_lhs < N_lhs; ++i_lhs) {
                const auto &[pa, pb]{p_lhs[i_lhs].second};
                // [L, M) の一次関数が切り替わる境界に対応する境界
                {
                    // inf になったら処理を終了
                    if (p_rhs[i_rhs - 1].second(p_lhs[i_lhs].first) == inf)
                        return piecewise_linear_convex{std::move(result)};
                    const auto &[ra, rb]{p_rhs[i_rhs - 1].second};
                    add_line(result, p_lhs[i_lhs].first, linear{pa * ra, pb * ra + rb});
                }

                // [M, R) の一次関数が切り替わる境界に対応する境界
                const auto next_i_rhs{i_lhs + 1 < N_lhs ? find_bound(p_rhs, p_lhs[i_lhs + 1].second(p_lhs[i_lhs + 1].first), i_rhs) : N_rhs};
                for (unsigned i{i_rhs}; i < next_i_rhs; ++i) {
                    const auto begins{p_rhs[i].first};
                    const auto x{(max(begins + pa, pb + 1) - pb - 1) / pa};
                    // inf になったら処理を終了
                    if (p_rhs[i].second(x) == inf)
                        return piecewise_linear_convex{std::move(result)};
                    const auto &[ra, rb]{p_rhs[i].second};
                    add_line(result, x, linear{pa * ra, pb * ra + rb});
                }
            }
            return piecewise_linear_convex{std::move(result)};
        }
    };

    using segment_tree_type = atcoder::segtree<piecewise_linear_convex, plus<>{}, [] { return piecewise_linear_convex{}; }>;

    unsigned N;
    cin >> N;
    vector<pair<unsigned long, unsigned long>> coefficients(N);
    for (auto &&[A, _]: coefficients)
        cin >> A;
    for (auto &&[_, B]: coefficients)
        cin >> B;

    // 組 (A, B) に対応する一次関数列を作ってセグメント木を構築
    segment_tree_type segment_tree{
            [](auto &&range) {
                return vector<ranges::range_value_t<decltype(range)>>(ranges::begin(range), ranges::end(range));
            }(
                coefficients
                | views::transform([](const auto &coef) { return piecewise_linear_convex::from_single_state(coef.first, coef.second); }
            ))};

    unsigned Q;
    cin >> Q;
    for (unsigned q{}; q < Q; ++q) {
        unsigned type, a, b;
        cin >> type >> a >> b;
        if (type == 1) {
            --a;
            coefficients[a].first = b;
            segment_tree.set(a, piecewise_linear_convex::from_single_state(coefficients[a].first, coefficients[a].second));
        } else if (type == 2) {
            --a;
            coefficients[a].second = b;
            segment_tree.set(a, piecewise_linear_convex::from_single_state(coefficients[a].first, coefficients[a].second));
        } else
            cout << segment_tree.prod(a - 1, b)(0) << endl;
    }

    return 0;
}