Problem Description

很多学校更受欢迎的习惯。

老师们真的很喜欢问。从XX XX到其中，的是多少。

这让非常多学生非常反感。

无论你喜不喜欢，如今须要你做的是，就是依照老师的要求。写一个程序，模拟老师的询问。当然。老师有时候须要更新某位同学的成绩。

 

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

Hint

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

 

感觉没什么好说的，这是我线段树的入门题，感觉效果非常好

#include
     
      #include
      
       #include
       
        #include
        
         #define L(x) (x<<1)#define R(x) (x<<1|1)#define MID(x,y) ((x+y)>>1)using namespace std;#define N 200005struct stud{int le,ri;int va;}f[N*4];int a[N];void pushup(int pos){    f[pos].va=max(f[L(pos)].va,f[R(pos)].va);}void build(int pos,int le,int ri){    f[pos].le=le;    f[pos].ri=ri;    if(le==ri)    {      f[pos].va=a[le];      return ;    }    int mid=MID(le,ri);    build(L(pos),le,mid);    build(R(pos),mid+1,ri);   pushup(pos);}void update(int pos,int le,int ri){    if(f[pos].le==le&&f[pos].ri==le)    {        f[pos].va=ri;        return ;    }    int mid=MID(f[pos].le,f[pos].ri);    if(mid>=le)        update(L(pos),le,ri);    else        update(R(pos),le,ri);    pushup(pos);}int query(int pos,int le,int ri){   if(f[pos].le>=le&&f[pos].ri<=ri)   {       return f[pos].va;   }   int mid=MID(f[pos].le,f[pos].ri);   if(mid>=ri)    return query(L(pos),le,ri);   else    if(mid
        
       
      
     

版权声明：本文博客原创文章，博客，未经同意，不得转载。