【哥种的第一棵线段树，至于你信不信，我反正信了】HDU 1754 I Hate It

http://acm.hdu.edu.cn/showproblem.php?pid=1754


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

效率不错，用加速输入外挂快了2百多ms！！
至于你信不信，我反正信了!!

#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <set>
//#include <map>
#include <queue>
#include <utility>
#include <iomanip>
#include <stack>
#include <list>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
//#include <ctime>
#include <ctype.h>
using namespace std;
#define eps 1e-8
#define PI 3.14159265358979
#define inf 0x3fffffff

struct node{
	int l, r, maxs;    //一个结点表示一个区间[l, r]和区间的最大值maxs
}N[600005];
int v[200005];

inline int maxs (int a, int b)    //木有inline会慢一点点
{
	return a > b ? a : b;
}

void create (int u, int l, int r)    //创建线段树，设u为父结点
{
	N[u].l = l, N[u].r = r;
	if (l == r)
	{
		N[u].maxs = v[l];    //初始化子叶结点
		return ;
	}
	int mid = (l + r) >> 1;    //一个区间分为2个，变成左子树和右子树
	create (u+u, l, mid);    //递归建立左子树
	create (u+u+1, mid+1, r);    //递归建立右子树
	N[u].maxs = maxs (N[u+u].maxs, N[u+u+1].maxs);    //返回更新父亲结点的最大值
}

void update (int u, int id, int New)    //更新结点的值，id是结点编号，New是新的值
{
	if (N[u].l == N[u].r)
	{
		N[u].maxs = New;
		return ;
	}
	if (id <= N[u+u].r)    //id在左子树上【N[u+u]是N[u]的左子结点】
		update (u+u, id, New);    //继续递归寻找id
	else update (u+u+1, id, New);  //id在右子树上【N[u+u+1]是N[u]的右子结点】
	N[u].maxs = maxs (N[u+u].maxs, N[u+u+1].maxs);    //递归更新父亲结点的最大值
}

int find (int u, int start, int end)    //寻找[start,end]这个区间的最大值
{    //此函数博大精深，至于你信不信，我反正信了……
	if (start <= N[u].l && end >= N[u].r)
		return N[u].maxs;
	int m1 = -inf, m2 = -inf;
	if (start <= N[u+u].r)
		m1 = find (u+u, start, end);
	if (end >= N[u+u+1].l)
		m2 = find (u+u+1, start, end);
	return maxs (m1, m2);
}

inline bool scan_d(int &num)      // 加速输入外挂，纯粹复制模板
{
        char in;
        bool IsN=false;
        in=getchar();
        if(in==EOF) return false;
        while(in!='-'&&(in<'0'||in>'9')) in=getchar();
        if(in=='-'){ IsN=true;num=0;}
        else num=in-'0';
        while(in=getchar(),in>='0'&&in<='9'){
                num*=10,num+=in-'0';
        }
        if(IsN) num=-num;
        return true;
}

int main()
{
	int n, m, i, a, b;
	char ch[3];
	while (~scanf ("%d%d", &n, &m))
	{
		for (i = 1; i <= n; i++)
			scan_d (v[i]);    //加速输入
		create (1, 1, n);    //创建并初始化线段树，1是根结点
		while (m--)
		{
			//scanf ("%s%d%d", ch, &a, &b);
			scanf ("%s", ch);
			scan_d (a);    //加速输入
			scan_d (b);
			if (ch[0] == 'Q')    //寻找[a,b]区间的最大值
				printf ("%d\n", find (1, a, b));
			else update (1, a, b);    //更新结点的值
		}
	}
    return 0;
}