Pagini recente » Rezultatele filtrării | Rezultatele filtrării | Rezultatele filtrării | Cod sursa (job #826373) | Cod sursa (job #1811723)
#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;
}