线段树点修改  区间最大值查询

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <map>

#include <set>

#include <queue>

#include <stack>

#include <vector>

#include <sstream>

#include <string>

#include <cstring>

#include <algorithm>

#include <iostream>

#define maxn 200010

#define INF 0x7fffffff

#define inf 10000000

#define MOD 1000000007

#define ull unsigned long long

#define ll long long

using namespace std;

int n, m, maxv[maxn*2], a[maxn], p, v, ql, qr;

void build(int id, int L, int R)

{

    if(L == R) maxv[id] = a[L];

    else

    {

        int M = L + (R-L)/2;

        build(id*2, L, M);

        build(id*2+1, M+1, R);

        maxv[id] = max(maxv[id*2], maxv[id*2+1]);

    }

}

void update(int id, int L, int R)

{

    if(L == R) maxv[id] = v;

    else

    {

        int M = L + (R-L)/2;

        if(p <= M) update(id*2, L, M);

        else update(id*2+1, M+1, R);

        maxv[id] = max(maxv[id*2], maxv[id*2+1]);

    }

}

int query(int id, int L, int R)

{

    int M = L + (R-L)/2, ans = 0;

    if(ql <= L && qr >= R) return maxv[id];

    if(ql <= M) ans = max(ans, query(id*2, L, M));

    if(qr > M) ans = max(ans, query(id*2+1, M+1, R));

    return ans;

}

int main()

{

    while(scanf("%d%d", &n, &m) == 2)

    {

        memset(maxv, 0, sizeof(maxv));

        for(int i = 1; i <= n; ++ i) scanf("%d", &a[i]);

        build(1, 1, n);

        //getchar();

        for(int i = 0; i < m; ++ i)

        {

            getchar();

            char c = getchar();

            if(c == 'Q')

            {

                scanf("%d%d", &ql, &qr);

                printf("%d\n", query(1, 1, n));

            }

            else if(c == 'U')

            {

                scanf("%d%d", &p, &v);

                update(1, 1, n);

            }

        }

    }

    return 0;

}