HDU 1754 I Hate It（线段树+单点更新）

本文主要是介绍HDU 1754 I Hate It（线段树+单点更新），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem Description

很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。这让很多学生很反感。

不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。

Input

本题目包含多组测试，请处理到文件结束。

在每个测试第一行，有两个正整数N和M ( 0<N<=200000,0<M<5000 )，分别代表学生的数目和操作的数目。学生ID编号分别从1编到N。

第二行包含N个整数，代表这N个学生的初始成绩，其中第i个数代表ID为i的学生的成绩。
接下来有M行，每一行有一个字符 C (只取’Q’或’U’) ，和两个正整数A，B。

当C为’Q’的时候，表示这是一条询问操作，它询问ID从A到B(包括A, B)的学生当中，成绩最高的是多少。
当C为’U’的时候，表示这是一条更新操作，要求把ID为A的学生的成绩更改为B。

Output

对于每一次询问操作，在一行里面输出最高成绩。

Sample Input

5 6
1 2 3 4 5
Q 1 5
U 3 6
Q 3 4
Q 4 5
U 2 9
Q 1 5

Sample Output

5
6
5
9

注：这是一道线段树的入门题，主要了解其基本的操作。

#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 200005;
struct data
{int left, right, Max;
} tree[3*MAXN];
int score[MAXN];
void pushUp(int node)
{tree[node].Max = max(tree[2*node].Max, tree[2*node+1].Max);
}
void build(int left, int right, int node)   //构建线段树
{//当前节点所表示的区间tree[node].left = left;tree[node].right = right;//左右区间相同，则此节点为叶子，Max 应储存对应某个学生的值if (left == right){tree[node].Max = score[left];return;}//递归建立左右子树int mid = left + (right - left) / 2;build(left, mid, 2*node);build(mid+1, right, 2*node+1);//从子树中获得最大值pushUp(node);
}
int query(int left, int right, int node)    //查询区间[left，right]的Max值
{//所查区间不在范围内if (tree[node].left > right || tree[node].right < left)return 0;//所查区间包含当前节点所管理的区间if (left <= tree[node].left && tree[node].right <= right)return tree[node].Max;int mid = (tree[node].left + tree[node].right) / 2;//所查区间与当前节点所管理的区间有部分相交if (right <= mid)return query(left, right, 2*node);else if (left > mid)return query(left, right, 2*node+1);elsereturn max(query(left, right, 2*node), query(left, right, 2*node+1));
}
void Updata(int pos, int val, int node)     //更新pos点的值
{//更新当前节点的Max值tree[node].Max = max(val, tree[node].Max);//pos点为叶子节点if (tree[node].left == pos && tree[node].right == pos){tree[node].Max = val;return;}if (pos <= tree[2*node].right)Updata(pos, val, 2*node);elseUpdata(pos, val, 2*node+1);
}
int main()
{int n, m;while (~scanf("%d %d", &n, &m)){for (int i=1; i<=n; i++)scanf("%d", &score[i]);build(1, n, 1);char c;int a, b;for (int i=1; i<=m; i++){getchar();scanf("%c %d %d", &c, &a, &b);if (c == 'U')Updata(a, b, 1);elseprintf("%d\n", query(a, b, 1));}}return 0;
}