I Hate It#
**Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 53991 Accepted Submission(s): 21180 **
Problem Description
很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。 这让很多学生很反感。
不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。
Input
本题目包含多组测试，请处理到文件结束。 在每个测试的第一行，有两个正整数 N 和 M ( 0学生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
Hint
Huge input,the C function scanf() will work better than cin
套的适牛模板.感谢适牛
1/*************************************************************************
2> File Name: code/hdu/1754.cpp
3> Author: 111qqz
4> Email: rkz2013@126.com
5> Created Time: 2015年10月28日 星期三 20时34分38秒
6************************************************************************/
7
8#include<iostream>
9#include<iomanip>
10#include<cstdio>
11#include<algorithm>
12#include<cmath>
13#include<cstring>
14#include<string>
15#include<map>
16#include<set>
17#include<queue>
18#include<vector>
19#include<stack>
20#include<cctype>
21
22#define yn hez111qqz
23#define j1 cute111qqz
24#define ms(a,x) memset(a,x,sizeof(a))
25using namespace std;
26const int dx4[4]={1,0,0,-1};
27const int dy4[4]={0,-1,1,0};
28typedef long long LL;
29typedef double DB;
30const int inf = 0x3f3f3f3f;
31#define lson l,m,rt<<1
32#define rson m+1 , r , rt<<1|1
33const int N=2E5+7;
34 34
35int n,m;
36int tree[N<<2];
37void PushUp( int rt)
38{
39tree[rt] = max(tree[rt<<1],tree[rt<<1|1]);
40}
41void build ( int l,int r,int rt)
42{
43if (l==r)
44{
45scanf("%d",&tree[rt]);
46return;
47}
48int m = (l+r) >> 1 ;
49build (lson);
50build(rson);
51PushUp(rt);
52}
53 53
54void update( int p,int sc,int l,int r,int rt)
55{
56if (l==r)
57{
58tree[rt] = sc;
59return;
60}
61int m =(l+r)>>1;
62if (p<=m) update(p,sc,lson);
63else update(p,sc,rson);
64PushUp(rt);
65}
66 66
67int query(int L ,int R, int l,int r,int rt)
68{
69if (L<=l&&r;<=R)
70{
71return tree[rt];
72}
73int m = (l+r)>>1;
74int ret = 0;
75if (L<=m)
76{
77int res = query(L,R,lson);
78ret = max(ret,res);
79}
80if (R>m)
81{
82int res = query(L,R,rson);
83ret = max(ret,res);
84}
85return ret;
86}
87int main()
88{
89#ifndef ONLINE_JUDGE
90freopen("in.txt","r",stdin);
91#endif
92
93while (scanf("%d %d",&n;,&m;)!=EOF)
94{
95build(1,n,1);
96while (m--)
97{
98char opt[10];
99int u,v;
100scanf("%s%d%d",opt,&u;,&v);
101if (opt[0]=='Q') printf("%dn",query(u,v,1,n,1));
102else update (u,v,1,n,1);
103}
104}
105
106
107#ifndef ONLINE_JUDGE
108fclose(stdin);
109#endif
110return 0;
111}