思路：线段树水题，可以手敲
#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 + ; int tree[maxn << ]; void build(int l, int r, int rt)
{
if (l == r){
cin >> tree[rt];
return;
}
int m = (l + r) >> ;
build(lson);
build(rson);
tree[rt] = max(tree[rt << ], tree[rt << | ]);
}
void update(int x, int ans, int l, int r, int rt)
{
if (l == r){
tree[rt] = ans;
return;
}
int m = (l + r) >> ;
if (x <= m)update(x, ans, lson);
else update(x, ans, rson);
tree[rt] = max(tree[rt << ] , tree[rt << | ]);
}
int query(int L, int R, int l, int r, int rt)
{
if (L <= l&&r <= R){
return tree[rt];
}
int m = (l + r) >> , ans = ;
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) >> ;
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(, n, );
string flag; int i, j;
while (q--){
cin >> flag >> i >> j;
if (flag == "U"){
update(i, j, , n, );
// Print(1, n, 1);
}
else if (flag == "Q"){
cout << query(i, j, , n, ) << endl;
}
} } return ;
}