题目：http://acm.hdu.edu.cn/showproblem.php?pid=1754
中文题，题意没什么好说的。
思路：这个题就是很简单的线段树的应用，需要查询某一区间内的成绩最高是多少，所以结点Tree 有三个成员l, r, max,分别表示区间的左端点，右端点，以及该区间上的最大值, 还是看代码
#include<cstdio> const int MAXN=200010; struct Tree{ int l, r; int max; }; Tree tree[MAXN * 4]; int arr[MAXN]; void construct(int l ,int r, int k) { tree[k].l = l; tree[k].r = r; int mid = (l + r) >> 1; if(l == r) { tree[k].max = arr[l];//建树的时候就保存学生原始成绩 return; } construct(l, mid, 2 * k); construct(mid + 1, r, 2 * k + 1); tree[k].max = tree[2 * k].max > tree[2 * k + 1].max ? tree[2 * k].max : tree[2 * k + 1].max;//回溯的时候取左右两个子区间中最大值较大的那个作为根结点的max值 } void update(int a, int b, int k) { int l = tree[k].l; int r = tree[k].r; if(tree[k].max < b) {//结点k所在区间上最大值小于k，则更新结点k的max值。 tree[k].max = b; } if(l == a && r == a) {//找到要更新的结点，修改它的max值 tree[k].max = b; return; } int mid = (l + r) >> 1; if(a <= mid) {//要更新的结点在左子区间 update(a, b, 2 * k); } else if(a > mid){//要更新的结点在右子区间 update(a, b, 2 * k + 1); } } int quary(int a, int b, int k) { int l = tree[k].l; int r = tree[k].r; if(l == a && r == b) {//找到要查询的区间，就返回该结点的max值 return tree[k].max; } int mid = (l + r) >> 1; int temp = 0, x, y; /*否则的话，如果要查询的区间落在左子区间，就对左子区间进行查询，落在右子区间就对右子区间进行查询， 落在中间的话，就把要查询的区间分厂两部分分别进行查询，取其中较大的那个的max值返回*/ if(b <= mid) { temp = quary(a, b, 2 * k); } else if(a > mid) { temp = quary(a, b, 2 * k + 1); } else { x = quary(a, mid, 2 * k); y = quary(mid + 1, b, 2 * k + 1); temp = x > y ? x : y; } return temp; } int main() { freopen("7.28A.txt", "r", stdin); int N, M; char ch; int a, b; while(scanf("%d %d", &N, &M) != EOF) { for(int i = 1; i <= N; ++ i) { scanf("%d", &arr[i]); } construct(1, N, 1); while(M --) { getchar(); scanf("%c %d %d", &ch, &a, &b); if(ch == 'Q') { int temp = quary(a, b, 1); printf("%d\n", temp); } else { update(a, b, 1); } } } return 0; } |