I Hate It

Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 66037 Accepted Submission(s): 25675

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 61 2 3 4 5Q 1 5U 3 6Q 3 4Q 4 5U 2 9Q 1 5

Sample Output

5659   
       
         
     Hint    
    Huge input,the C function scanf() will work better than cin

Author

linle

Source

Recommend

lcy | We have carefully selected several similar problems for you:

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define lson l,m,rt<<1 //lson表示左子树 #define rson m+1,r,rt<<1|1 //rson表示右子树 #define M 222222using namespace std;int MAX[M<<2];void pushup(int rt){	MAX[rt]=max(MAX[rt<<1],MAX[rt<<1|1]);// 比较左子树和右子树的大小 跟新节点数据 }void build(int l,int r,int rt){	if(l==r) //当左右节点为一个数时 输入这个数  叶子 	{		scanf("%d",&MAX[rt]);		return ;	}	int m=(l+r)>>1;	build(lson);	build(rson);	pushup(rt);}void update(int p,int add,int l,int r,int rt){	if(l==r)//找到在L与R之间的所有区间部分 比较每个区间的最大值 并持续更新  l与r是L与R的子区间 	{		MAX[rt]=add;		return ;	}	int m=(l+r)>>1;	if(p<=m)update(p,add,lson); //分成多个部分 如果左区间存在交集 比较左区间的最大值值 	else update(p,add,rson);	pushup(rt);}int query(int L,int R,int l,int r,int rt){	if(L<=l&&R>=r)	{		return MAX[rt]; 	}	int m=(r+l)>>1;	int res=0;	if(L<=m)	res=max(res,query(L,R,lson));	if(R>m)	res=max(res,query(L,R,rson));	return res;}int main(){	int n,m;	while(~scanf("%d%d",&n,&m))	{		build(1,n,1);//树从是第一个节点开始 		while(m--)		{			char op[2];			int a,b;			scanf("%s%d%d",op,&a,&b);			if(op[0]=='Q')			printf("%d\n",query(a,b,1,n,1));			else update(a,b,1,n,1);		}	}	return 0;}/*5 61 2 3 4 5Q 1 5U 3 6Q 3 4Q 4 5U 2 9Q 1 55659*/