#include <iostream>
#include <string>
#include <fstream>
#define max(x, y) ((x) > (y) ? (x) : (y))
using namespace std;
const int NMAX = 100001;
int v[NMAX], tree[2 * NMAX];
ifstream in("arbint.in");
ofstream out("arbint.out");
void buildArbInt(int node, int st, int dr) {
if (st == dr) {
tree[node] = v[st];
}
else {
int mid = (st + dr) / 2;
buildArbInt(2 * node, st, mid);
buildArbInt(2 * node + 1, mid + 1, dr);
tree[node] = max(tree[2 * node], tree[2 * node + 1]);
}
}
int queryMax(int node, int st, int dr, int qst, int qdr) {
// daca intervalul curent este complet inclus in intervalul pe care fac query
if (qst <= st && dr <= qdr) {
return tree[node];
}
// daca intervalul este inclus partial in intervalul de query, vad in ce fii merg
int mid = (st + dr) / 2;
if (qdr <= mid) {
return queryMax(node * 2, st, mid, qst, qdr);
}
else if (qst > mid) {
return queryMax(node * 2 + 1, mid + 1, dr, qst, qdr);
}
else {
return max(queryMax(node * 2, st, mid, qst, qdr), queryMax(node * 2 + 1, mid + 1, dr, qst, qdr));
}
}
void updateValue(int node, int st, int dr, int index, int val) {
if (st == dr) {
tree[node] = val;
}
else {
int mid = (st + dr) / 2;
// indexul meu se afla in subarborele stang
if (index <= mid) {
updateValue(node * 2, st, mid, index, val);
}
else {
updateValue(node * 2 + 1, mid + 1, dr, index, val);
}
// updatam valorile tatilor pe baza modificarilor efectuate pe fii
tree[node] = max(tree[node * 2], tree[node * 2 + 1]);
}
}
int main() {
int n, m;
in >> n >> m;
for (int i = 0; i < n; i++) {
int tmp; in >> tmp;
updateValue(1, 0, n - 1, i, tmp);
}
//for (int i = 1; i < 2 * n; i++) cout << tree[i] << ' ';
//buildArbInt(1, 0, n - 1);
//int k = 0;
for (int i = 0; i < m; i++) {
int op, a, b;
in >> op >> a >> b;
if (op == 0) {
out << queryMax(1, 0, n - 1, a - 1, b - 1);
out << "\n";
}
else {
//cout << k << "\n";
updateValue(1, 0, n - 1, a - 1, b);
}
}
return 0;
}
Micuda Andrei Micu