hdu 1754 I Hate It(线段树水题）

》》点击进入原题测试《《

思路：线段树水题，可以手敲

#include<string>
#include<iostream>
#include<algorithm>

#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

using namespace std;


const int maxn = 2e5 + 5;

int tree[maxn << 2];


void build(int l, int r, int rt)
{
    if (l == r){
        cin >> tree[rt];
        return;
    }
    int m = (l + r) >> 1;
    build(lson);
    build(rson);
    tree[rt] = max(tree[rt << 1], tree[rt << 1 | 1]);
}
void update(int x, int ans, int l, int r, int rt)
{
    if (l == r){
        tree[rt] = ans;
        return;
    }
    int m = (l + r) >> 1;
    if (x <= m)update(x, ans, lson);
    else update(x, ans, rson);
    tree[rt] = max(tree[rt << 1] , tree[rt << 1 | 1]);
}
int query(int L, int R, int l, int r, int rt)
{
    if (L <= l&&r <= R){
        return tree[rt];
    }
    int m = (l + r) >> 1, ans = 0;
    if (L <= m)ans = max(ans, query(L, R, lson));
    if (R > m)ans = max(ans, query(L, R, rson));
    return ans;
}
void Print(int l, int r, int rt)
{
    if (l == r){
        cout << rt << " = " << tree[rt] << endl;
        return;
    }
    cout << rt << " = " << tree[rt] << endl;
    int m = (l + r) >> 1;
    if (l <= m)Print(lson);
    if (r > m)Print(rson);
}
int main()
{
    std::ios::sync_with_stdio(false);
    
    int n, q; 
    while (cin >> n >> q){
        build(1, n, 1);
        string flag; int i, j;
        while (q--){
            cin >> flag >> i >> j;
            if (flag == "U"){
                update(i, j, 1, n, 1);
            //    Print(1, n, 1);
            }
            else if (flag == "Q"){
                cout << query(i, j, 1, n, 1) << endl;
            }
        }
        
    }

    return 0;
}