kuangbin_SegTree B (HDU 1754)

跟A题类似 只是把update从增减直接改为赋值 query从求和改为求最大值 其他几乎一样

#include <cstdio>

#include <cstring>

#include <queue>

#include <vector>

#include <algorithm>

#define INF 0x3f3f3f3f

#define lson l, m, root<<1

#define rson m+1, r, root<<1|1

using namespace std;

const int MAXN = 2e5+;

int val[MAXN*];

void pushup(int root)

{

    val[root] = max(val[root<<], val[root<<|]);

}

void build(int l, int r, int root)

{

    if(l == r) scanf("%d", &val[root]);

    else{

        int m = (l + r) >> ;

        build(lson);

        build(rson);

        pushup(root);

    }

}

void update(int point, int value, int l, int r, int root)

{

    if(l == r) val[root] = value;

    else{

        int m = (l + r) >> ;

        if(point <= m) update(point, value, lson);

        else update(point, value, rson);

        pushup(root);

    }

}

int query(int L, int R, int l, int r, int root)

{

    if(L <= l && R >= r) return val[root];

    int res = ;

    int m = (l + r) >> ;

    if(L <= m) res = max(res, query(L, R, lson));

    if(R > m) res = max(res, query(L, R, rson));

    return res;

}

int main()

{

    int n, m;

    while(~scanf("%d%d", &n, &m)){

        build(, n, );

        char op[];

        while(m--){

            scanf("%s", op);

            int u, v;

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

            if(op[] == 'U') update(u, v, , n, );

            else{

                if(u > v) swap(u, v);

                printf("%d\n", query(u, v, , n, ));

            }

        }

    }

    return ;

}