Cod sursa(job #1811723)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 21 noiembrie 2016 15:33:57
Problema Arbori de intervale Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.78 kb
#include <bits/stdc++.h>
#define SZ(x) ((int) (x).size())
using namespace std;

template<class T>
struct SegmentedTree {
    vector<T> tree;
    int n;

    static T Combine(const T& leftSon, const T& rightSon) {
        return leftSon < rightSon ? rightSon : leftSon;
    }

    SegmentedTree(const vector<T>& v) {
        n = SZ(v);

        tree.resize(2 * n);
        copy(v.begin(), v.end(), tree.begin() + n);
        for (int i = n - 1; i > 0; i--) {
            tree[i] = Combine(tree[i << 1], tree[i << 1 | 1]);
        }
    }

    void Update(int idx, const T& x) {
        idx += n;
        tree[idx] = x;
        do {
            idx >>= 1;
            tree[idx] = Combine(tree[idx << 1], tree[idx << 1 | 1]);
        } while (idx);
    }

    // pentru operatii care nu sunt comutative
    T Query(int left, int right) const {
        T leftResult = 0, rightResult = 0;

        left += n; right += n + 1;
        while (left < right) {
            if (left & 1) {
                leftResult = Combine(leftResult, tree[left++]);
            }
            if (right & 1) {
                rightResult = Combine(tree[--right], rightResult);
            }
            left >>= 1; right >>= 1;
        }
        return Combine(leftResult, rightResult);
    }
};

int main() {
    #ifdef INFOARENA
    ifstream cin("arbint.in");
    ofstream cout("arbint.out");
    #endif
    cin.tie(0);
    ios_base::sync_with_stdio(false);

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

    SegmentedTree<int> ST(v);
    for (int i = 0; i < q; i++) {
        int qType, a, b; cin >> qType >> a >> b;
        if (qType == 0) {
            cout << ST.Query(a - 1, b - 1) << '\n';
        } else {
            ST.Update(a - 1, b);
        }
    }
    return 0;
}