写题之前先要搞清楚题解里说的极大区间之间的关系（只需要合并包括左侧右端点的极大区间和包括右侧左端点的极大区间；注意对每个极大区间我们记录的数量是在区间内能吃完这一个区间的位置的数量；不包括端点的区间永远不可能再成为答案）。否则你可能会脑子里一团浆糊，搞不清楚或者多考虑很多情况。

把整个区间同时作为两侧特殊的极大区间，可以减少很多分类讨论。但是需要注意添加哨兵的位置，否则可能会在合并时多添加一些区间。

为了写起来方便（统一讨论）可以把添加极大线段作为一个成员函数，然后复杂度也许会多加一个 $\log \log A$（用来在合并的最后给区间排序），应该没有大问题的。

附使用 ACL 的源代码。虽然我写的很烂，但看起来好像没有特别长（应该吧）。

#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
using u64 = uint64_t;

#include <atcoder/segtree>
#define int i64
vector<int> vec;

struct Info {
    int x, c, sum;
    bool operator<(const Info& o) const {
        return array{x, c, sum} < array{o.x, o.c, o.sum};
    }
};

struct Node {
    int l{}, r{}, sum{};
    bool e{};
    int ans{};
    vector<Info> left_rs, right_ls;
    Node() = default;
    Node(int i) : ans(1) {
        l = i, r = i, sum = vec[i];
    }
    void addSeg(int sl, int sr, int c, int sum) {
        if (sl == l && sr == r) ans += c;
        else if (sl == l) {
            left_rs.emplace_back(sr, c, sum);
        } else if (sr == r) {
            right_ls.emplace_back(sl, c, sum);
        }
    }
    void sortBnd() {
        sort(left_rs.begin(), left_rs.end());
        sort(right_ls.begin(), right_ls.end());
        auto v = std::move(left_rs);
        sort(v.begin(), v.end());
        for (auto [r, c, s]: v) {
            if (left_rs.empty() || left_rs.back().x != r) left_rs.emplace_back(r, c, s);
            else left_rs.back().c += c;
        }
        v = std::move(right_ls);
        sort(v.begin(), v.end());
        reverse(v.begin(), v.end());
        for (auto [l, c, s]: v) {
            if (right_ls.empty() || right_ls.back().x != l) right_ls.emplace_back(l, c, s);
            else right_ls.back().c += c;
        }
    }
};

Node add(Node a, Node b) {
    if (a.e) return b;
    if (b.e) return a;
    Node res;
    res.sum = a.sum + b.sum;
    res.l = a.l, res.r = b.r;
    int m = a.r;
    res.left_rs = a.left_rs;
    res.right_ls = b.right_ls;
    auto av = a.right_ls, bv = b.left_rs;
    av.emplace_back(res.l, a.ans, a.sum);
    bv.emplace_back(res.r, b.ans, b.sum);
    int nowl = m + 1, nowr = m, asum = 0, bsum = 0, now_cnt = 0, idx = 0;
    int bm = bv.size();
    for (auto [l, c, s]: av) {
        nowl = l;
        asum = s;
        now_cnt += c;
        while (idx < bm) {
            if (asum + bsum >= vec[nowr + 1]) {
                nowr = bv[idx].x;
                bsum = bv[idx++].sum;
            } else break;
        }
        if (nowl != res.l && asum + bsum >= vec[nowl - 1]) continue;
        res.addSeg(nowl, nowr, now_cnt, asum + bsum);
        now_cnt = 0;
    }
    nowl = m + 1, nowr = m, asum = 0, bsum = 0, now_cnt = 0, idx = 0;
    int am = av.size();
    for (auto [r, c, s]: bv) {
        nowr = r;
        bsum = s;
        now_cnt += c;
        while (idx < am) {
            if (asum + bsum >= vec[nowl - 1]) {
                nowl = av[idx].x;
                asum = av[idx++].sum;
            } else break;
        }
        if (nowr != res.r && asum + bsum >= vec[nowr + 1]) continue;
        res.addSeg(nowl, nowr, now_cnt, asum + bsum);
        now_cnt = 0;
    }
    res.sortBnd();
    return res;
}

Node e() {
    Node res; res.e = true;
    return res;
}

using segtree = atcoder::segtree<Node, add, e>;

constexpr int INF = 1e18;
void solve() {
    int n; cin >> n;
    vec = vector<int>(n + 2);
    for (int i = 1; i <= n; i++) cin >> vec[i];
    vec[0] = vec[n + 1] = INF;
    segtree tr(n + 1);
    for (int i = 1; i <= n; i++) {
        tr.set(i, Node{i});
    }
    int q; cin >> q;
    while (q--) {
        int op; cin >> op;
        if (op == 1) {
            int p, x; cin >> p >> x;
            vec[p] = x; tr.set(p, Node{p});
        } else {
            int l, r; cin >> l >> r;
            auto res = tr.prod(l, r + 1);
            cout << res.ans << '\n';
        }
    }
}
#undef int

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}