---恢复内容开始---
题意：给定区间,每个人的成绩, Q次询问,求每次询问区间中的最大值
思路：构造线段树
代码：
#include<stdio.h>
#include<algorithm>
#include<string>
#include<iostream>
using namespace std; int n, m, ans;
string str; struct Tree
{
int left, right, maxx;
}tree[ * ]; //线段树开4倍空间 void build(int left, int right, int k)
{
tree[k].left = left, tree[k].right = right;
if(left == right)
{
scanf("%d", &tree[k].maxx);
return ;
}
int mid = (left + right) / ;
build(left, mid, * k);
build(mid + , right, * k + );
tree[k].maxx = max(tree[ * k].maxx, tree[ * k + ].maxx); //向上回溯最大值记录
} void update(int find_node, int up_num, int k)//单点修改
{
if(tree[k].left == find_node && tree[k].right == find_node)
{
tree[k].maxx = up_num;
return ;
}
int mid = (tree[k].left + tree[k].right) / ;
if(find_node <= mid)
update(find_node, up_num, * k);
else
update(find_node, up_num, * k + ); //修改过后回溯修改最大值
tree[k].maxx = max(tree[ * k].maxx, tree[ * k + ].maxx);
} void query(int find_left, int find_right, int k)//区间查询取最大值
{
if(find_left == tree[k].left && find_right == tree[k].right)
{
ans = max(ans, tree[k].maxx);
return ;
}
int mid = (tree[k].left + tree[k].right) / ;
if(find_right <= mid)
query(find_left, find_right, * k);
else if(find_left > mid)
query(find_left, find_right, * k + );
else
{
query(find_left, mid, * k);
query(mid + , find_right, * k + );
}
} int main()
{
int a, b;
while(scanf("%d%d", &n, &m)!=EOF)
{
build(, n, );
for(int i = ; i <= m; i ++)
{
cin >> str;
if(str == "U")
{
scanf("%d%d", &a, &b);
update(a, b, );
}
else
{
ans = -;
scanf("%d%d", &a, &b);
query(a, b, );
printf("%d\n", ans);
}
}
}
return ;
}