swea 14726 c++

#include <iostream>
#include <vector>
#include <algorithm>
#define INF 1000000001

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll; // 최소값, 최대값을 저장할 pair

int n, q;
vector<ll> ans;
vector<ll> a;
vector<pll> tree;

pll init(int position, int start, int end) {
	
    //leaf node
	if (start == end) { 
        return tree[position] = { a[start], a[start] };
    } 
    
    // leaf node가 아닐 경우 범위 내 최대, 최소 저장
    int mid = (start + end) / 2;
    pll left = init(position * 2, start, mid);
    pll right = init(position * 2 + 1, mid + 1, end);
    return tree[position] = { min(left.first, right.first), max(left.second, right.second) };
    
}

void update(int position, int start, int end, int index, ll value) {
	
    // update한 index가 범위 내에 없으면 업데이트 할 필요가 없다
    if (index < start || index > end) return;
    
    // update한 leaf node
    if (start == end) {
        tree[position] = { value, value };
        return;
    }

	// leaf node update하고 올라오면서 min, max upadate
    int mid = (start + end) / 2;
    update(position * 2, start, mid, index, value);
    update(position * 2 + 1, mid + 1, end, index, value);
    tree[position] = { min(tree[position * 2].first, tree[position * 2 + 1].first),
                      max(tree[position * 2].second, tree[position * 2 + 1].second) };
                      
}

pll query(int position, int start, int end, int left, int right) {
	
    //탐색 범위를 넘어가면 inf값 return(무시)
    if (left > end || right < start) return { INF, -INF };
    
    //범위 내에 들어오면 구하는 node이다.
    if (left <= start && end <= right) return tree[position];

	//범위 내 최대, 최소 찾기
    int mid = (start + end) / 2;
    pll lQuery = query(position * 2, start, mid, left, right);
    pll rQuery = query(position * 2 + 1, mid + 1, end, left, right);
    return { min(lQuery.first, rQuery.first), max(lQuery.second, rQuery.second) };
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    for(int tc = 1; tc<=T; tc++) {
        cin >> n >> q;
        a.resize(n);
        tree.resize(n * 4);

        for (int i = 0; i < n; i++) cin >> a[i];
        init(1, 0, n - 1);

        while (q--) {
            int type, i;
            ll x;
            cin >> type >> i >> x;
            if (type == 0) {
                update(1, 0, n - 1, i, x);
            }
            else {
                int l = i, r = x;
                pll result = query(1, 0, n - 1, l, r - 1);
                ans.push_back(result.second - result.first);
            }
        }


        cout << "#" << tc << " ";

        for (int i = 0; i < ans.size(); i++) {
            cout << ans[i] << " ";
        }
        cout << "\n";
        ans.clear();
    }

    return 0;
}