HDU - 1754 线段树

#include <algorithm>
#include <iostream>
#include<sstream>
#include<cstring>
#include<string>
#include<cstdio>
#include<cctype>
#include<vector>
#include<deque>
#include<map>
#include<set>

#define M 200000
#define inf 0x3f3f3f3f
typedef long long ll;

using namespace std;

struct Data
{
    int max;
    int left, right;
}tree[M*4];
int n, m;
int ans;
int x, y;
char ch;

void built(int l,int r,int k) {
    tree[k].left = l, tree[k].right = r;
    if (l == r) {
        scanf("%d", &tree[k].max);
        return;
    }
    int mid = (l + r) / 2;
    built(l, mid,k*2);
    built(mid + 1, r, k * 2 + 1);
    tree[k].max = max(tree[k * 2].max, tree[k * 2 + 1].max);
}

void search(int k) {
    if (tree[k].left >= x && tree[k].right <= y) {
        ans = max(ans, tree[k].max);
        return;
    }
    int mid = (tree[k].left + tree[k].right) / 2;
    if (x <= mid) search(k * 2);
    if(y>mid) search(k * 2 + 1);
}

void change_inv(int k) {
    if (tree[k].left == tree[k].right) {
        tree[k].max = y;
        return;
    }
    int mid = (tree[k].left + tree[k].right) / 2;
    if (x <= mid) change_inv(k * 2);
    else change_inv(k * 2 + 1);
    tree[k].max = max(tree[k * 2].max, tree[k * 2 + 1].max);
}

int main() {
    while (scanf("%d%d",&n,&m)!=EOF){
        built(1, n, 1);
        while (m--){
            cin >> ch;
            scanf("%d%d", &x, &y);
            if(ch=='Q'){
                ans = 0;
                search(1);
                printf("%d\n", ans);
            }
            else {
                change_inv(1);
            }
        }
    }
    return 0;
}