题解 | 【模板】动态区间最值Ⅰ ‖ 单点修改 + 区间查询

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

vector<pair<int, int>> tree;

pair<int, int> create(vector<int>& dic, int p, int l, int r) {
    if (l == r) {
        int value = dic[l];
        tree[p] = { value,value };
        return tree[p];
    }
    int mid = l + (r - l) / 2;
    auto l_val = create(dic, p * 2 + 1, l, mid);
    auto r_val = create(dic, p * 2 + 2, mid + 1, r);
    tree[p] = { max(l_val.first,r_val.first), min(l_val.second,r_val.second) };
    return tree[p];
}

int search(int& mode, int a, int b, int p, int l, int r) {
    if (a <= l && r <= b) return mode == 2 ? tree[p].second : tree[p].first;
    int mid = l + (r - l) / 2;
    if (b <= mid) return search(mode, a, b, p * 2 + 1, l, mid);
    if (mid < a) return search(mode, a, b, p * 2 + 2, mid + 1, r);
    int l_val = search(mode, a, mid, p * 2 + 1, l, mid);
    int r_val = search(mode, mid+1, b, p * 2 + 2, mid + 1, r);
    return mode == 2 ? min(l_val, r_val) : max(l_val, r_val);
}

void modify(int pos, int change, int p, int l, int r) {
    if (l == r) {
        tree[p].first += change;
        tree[p].second += change;
        return;
    }
    int mid = l + (r - l) / 2;
    if (pos <= mid) modify(pos, change, p * 2 + 1, l, mid);
    else modify(pos, change, p * 2 + 2, mid + 1, r);
    
    tree[p].first = max(tree[p * 2 + 1].first, tree[p * 2 + 2].first);
    tree[p].second = min(tree[p * 2 + 1].second, tree[p * 2 + 2].second);
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<int> dic;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        dic.emplace_back(x);
    }
    tree.resize(4 * n);
    create(dic, 0, 0, n - 1);
    while (m--) {
        int mode, a, b;
        cin >> mode >> a >> b;
        if (mode == 1) modify(a - 1, b, 0, 0, n - 1);
        else cout << search(mode, a-1, b-1, 0, 0, n - 1)<<"\n";
    }
    return 0;
}