Pagini recente » Cod sursa (job #2899140) | Cod sursa (job #3227940) | Borderou de evaluare (job #2385984) | Cod sursa (job #1357347)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("arbint.in");
ofstream out("arbint.out");
/*
tree memory = 2^(k + 1) - (2^k - n) - 1
k = min so that 2^k >= n
*/
const int Nmax = 100005;
const int tree_size = 231077;
int n, m;
int op, a, b;
int tree[tree_size];
int position, value, result;
void update(int node, int l, int r) {
if (l == r)
tree[node] = value;
else {
int m = (l + r) / 2;
if (position <= m) update(node * 2, l, m);
else update(node * 2 + 1, m + 1, r);
tree[node] = max(tree[node * 2], tree[node * 2 + 1]);
}
}
void query(int node, int l, int r) {
if (a <= l && r <= b)
result = max(result, tree[node]);
else {
int m = (l + r) / 2;
if (a <= m) query(node * 2, l, m);
if (m < b) query(node * 2 + 1, m + 1, r);
}
}
int main() {
in >> n >> m;
for (int i = 1; i <= n; ++i) {
in >> a;
position = i;
value = a;
update(1, 1, n);
}
for (int i = 1; i <= m; ++i) {
in >> op >> a >> b;
if (op == 0) {
result = -1;
query(1, 1, n);
out << result << '\n';
}
else {
position = a;
value = b;
update(1, 1, n);
}
}
return 0;
}