PROG-T1147: Segment Tree

#include <bits/stdc++.h>
using namespace std;

const int N = (1 << 18);
const int LOGN = 18;
const int INF = 1e9;

int sgt[(1 << (LOGN + 1))];
int nSeq, nExp, Q;

int main(){

    scanf("%d %d", &nSeq, &Q);
    nExp = 0;
    while((1 << nExp) < nSeq){
        ++nExp;
    }

    for(int i = (1 << nExp) + nSeq; i < (1 << (nExp + 1)); ++i){
        sgt[i] = -INF;
    }
    for(int i = (1 << nExp) - 1; i >= 1; --i){
        sgt[i] = max(sgt[i << 1], sgt[(i << 1) | 1]);
    }

    while(Q--){
        char cmd;
        int a, b;
        scanf(" %c %d %d", &cmd, &a, &b);
        if(cmd == 'U'){
            a = (1 << nExp) + a - 1;
            sgt[a] = b;
            while(a > 1){
                if(a % 2 == 0){
                    sgt[a / 2] = max(sgt[a], sgt[a + 1]);
                } else {
                    sgt[a / 2] = max(sgt[a], sgt[a - 1]);
                }
                a /= 2;
            }
        } else if(cmd == 'P'){
            a = (1 << nExp) + a - 1;
            b = (1 << nExp) + b - 1;
            int ans = -INF;
            while(a <= b){
                if(a % 2 == 1){
                    ans = max(ans, sgt[a++]);
                }
                if(b % 2 == 0){
                    ans = max(ans, sgt[b--]);
                }
                a /= 2;
                b /= 2;
            }
            cout << ans << "\n";
        }
    }

    return 0;
}