和前一个题是一样的，但是变成区间求最小值了怎么办？

把 set 放到线段树上。。。

每个线段树维护一个 set 即可。时间复杂度 $O(n \log^2 n)$，轻松拿下最劣解。

什么为什么是最劣解，因为根本不需要维护 set。。。

#include<bits/stdc++.h>
#define pii pair<int, int>
using namespace std;
int n, q, a[100005];
set<pii> S[400005];
void upd(int u, int l, int r, int pos, int x, int typ){
    if (pos < l || pos > r) return;
    if (typ) S[u].insert({x, pos});
    else S[u].erase(S[u].find({x, pos}));
    if (l == r) return;
    upd(u << 1, l, (l + r) >> 1, pos, x, typ), upd(u << 1 | 1, (l + r + 2) >> 1, r, pos, x, typ);
}
pii qry(int u, int l, int r, int L, int R){
    if (l > R || r < L) return {2e9, 0};
    if (L <= l && r <= R) return *S[u].begin();
    return min(qry(u << 1, l, (l + r) >> 1, L, R), qry(u << 1 | 1, (l + r + 2) >> 1, r, L, R));
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i], upd(1, 1, n, i, a[i], 1);
    cin >> q; 
    while (q--){
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1) upd(1, 1, n, x, a[x], 0), upd(1, 1, n, x, a[x] = y, 1);
        else cout << qry(1, 1, n, x, y).second << "\n";
    }
    return 0;
}