Code : Second Largest Query

#include <atcoder/segtree>
#include <bits/stdc++.h>

using namespace std;
using namespace atcoder;

using S = map<int, int>;

S op(S a, S b) {
    S res;
    for (auto &kv : a) {
        res[kv.first] += kv.second;
    }
    for (auto &kv : b) {
        res[kv.first] += kv.second;
    }
    while ((int)res.size() > 2) {
        res.erase(res.begin());
    }
    return res;
}

S e() { return S(); }

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    segtree<S, op, e> st(n + 1);
    for (int i = 0; i < n; i++) {
        st.set(i, S{{a[i], 1}});
    }
    for (int i = 0; i < q; i++) {
        int type;
        cin >> type;
        if (type == 1) {
            int ind, x;
            cin >> ind >> x;
            ind--;
            st.set(ind, S{{x, 1}});
        } else {
            int l, r;
            cin >> l >> r;
            l--;
            r--;
            // Atcoder's segtree has closed-open range. Hence, we add +1.
            auto res = st.prod(l, r + 1);
            if (res.size() != 2) {
                cout << 0 << "\n";
            } else {
                cout << res.begin()->second << "\n";
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    solve();
    return 0;
}