I Hate ItTime Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 107455 Accepted Submission(s): 40327 Problem Description 很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。
Input 本题目包含多组测试，请处理到文件结束。
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
Author linle
Source 2007省赛集训队练习赛（6）_linle专场
Recommend lcy | We have carefully selected several similar problems for you: 1698 1394 2795 1540 1255 |
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#define N 200010
#define ll long long
using namespace std;
ll a[N];
int n,m;
struct node //线段树
{int l,r;ll dat;
}tree[N<<2];
void PushUp(int x) //线段树维护结点信息
{tree[x].dat=max(tree[x<<1].dat,tree[x<<1|1].dat);
}
void build(int x,int l,int r) //线段树建树
{tree[x].l=l;tree[x].r=r;if (l==r) //叶子节点{tree[x].dat=a[l];return;}int mid=(l+r)>>1;build(x<<1,l,mid);build(x<<1|1,mid+1,r);PushUp(x);
}
ll query(int x,int l,int r) //线段树区间查询
{ if (l<=tree[x].l&&r>=tree[x].r) return abs(tree[x].dat); //找到int mid=(tree[x].l+tree[x].r)>>1;ll ans=0;if (l<=mid) ans=max(ans,query(x<<1,l,r));if (r>mid) ans=max(ans,query(x<<1|1,l,r)); return ans;
}
void update(int x,int y,ll k) //线段树单点修改
{if (tree[x].l==tree[x].r) {tree[x].dat = k;return ;}int mid=(tree[x].l+tree[x].r)>>1;if (y<=mid) update(x<<1,y,k);else update(x<<1|1,y,k);PushUp(x);
}int main()
{while(scanf("%d%d",&n,&m)!=-1){for(int i=1;i<=n;i++)scanf("%lld",&a[i]);build(1,1,n);char s[10];while(m--){scanf("%s",&s);int i,j;if(s[0]=='U'){scanf("%d%d",&i,&j);update(1,i,j);}else if(s[0]=='Q'){scanf("%d%d",&i,&j);printf("%lld\n",query(1,i,j));}}}return 0;
}