1 #include <iostream> 2 #include <cstring> 3 #include <cstdlib> 4 #include <cstdio> 5 #include <numeric> 6 #include <cctype> 7 #include <algorithm> 8 #include <cmath> 9 #include <vector>10 #include <climits>11 using namespace std;12 13 const int maxn = 2e5 + 10;14 int maxv[maxn * 3];15 16 void update (int p, int v, int o, int L, int R) {17     int M = L + ((R - L) >> 1);18     if (L == R) {19         maxv[o] = v;20     } else {21         if (p <= M) {22             update (p, v, o << 1, L, M);23         } else {24             update (p, v, (o << 1) | 1, M + 1, R);25         }26         maxv[o] = max (maxv[o * 2], maxv[o << 1 | 1]);27     }28 }29 30 int query (int ql, int qr, int o, int L, int R) {31     int M = L + (R - L) / 2, ans = INT_MIN;32     if (ql <= L && R <= qr) {33         return maxv[o];34     }35     if (ql <= M) {36         ans = max (ans, query (ql, qr, o << 1, L, M));37     }38     if (M < qr) {39         ans = max (ans, query (ql, qr, o << 1 | 1, M + 1, R));40     }41     return ans;42 }43 44 int main () {45     int n, ask_n, x, a, b;46     char op[5];47     while (~scanf ("%d%d", &n, &ask_n)) {48         memset (maxv, 0, sizeof(maxv));49         for (int i = 1; i <= n; ++ i)  {50             scanf ("%d", &x);51             update (i, x, 1, 1, n);52         }53 54         while (ask_n --) {55             scanf ("%s %d %d", op, &a, &b);56 57             if (op[0] == ‘Q‘) {58                 printf ("%d\n", query (a, b, 1, 1, n));59             } else if (op[0] == ‘U‘) {60                 update (a, b, 1, 1, n);61             }62         }63     }64     return 0;65 }