arbin

#include <bits/stdc++.h>
using namespace std;
ifstream in("arbint.in");
ofstream out("arbint.out");
const int nmax = 100006;
int block[nmax], blockSize, a[nmax], N, M, maxByBlock[nmax];
int getMax(int L, int R) {
	int ans = -2e9;
	while(L < R && block[L] == block[L + 1]) {
		ans = max(ans, a[L]);
		L++;
	}
	while(R > L && block[R] == block[R - 1]) {
		ans = max(ans, a[R]);
		R--;
	}
	if(L == R) {
		ans = max(ans, a[L]);
		L++;
	} else {
		ans = max(ans, a[L]);
		ans = max(ans, a[R]);
		L++;
		R--;
	}
	if(L <= R) {
		for(int j = block[L]; j <= block[R]; ++j) {
			ans = max(ans, maxByBlock[j]);
		}
	}
	return ans;
}

void updatePos(int pos, int x) {
	int L = block[pos] * blockSize;
	int R = min( (block[pos] + 1) * blockSize - 1, N - 1);
	a[pos] = x;
	maxByBlock[ block[pos] ] = -2e9;
	for(int j = L; j <= R; ++j) {
		maxByBlock[ block[j] ] = max(maxByBlock[ block[j] ], a[j]);
	}
}

int main()  {
    in >> N >> M;
    for(int i = 0; i < N; ++i) {
        in >> a[i];
    }
    blockSize = (int) sqrt(N);
    for(int i = 0; i < N; ++i) {
        block[i] = i / blockSize;
    }
    for(int i = 0; i < N; ++i) {
        int whatBlock = block[i];
        maxByBlock[whatBlock] = max(maxByBlock[whatBlock], a[i]);
    }
    for(int i = 0; i < M; ++i) {
         int op;
         in >> op;
         if(op == 0) {
			int L, R;
			in >> L >> R;
			out << getMax(L - 1, R - 1) << '\n';

		 } else {
			 int pos, x;
			 in >> pos >> x;
			 updatePos(pos - 1, x);
		 }
    }
}