最高分是多少

比眉伴天荒 2022-08-05 13:16 179阅读 0赞

## 1111: 最高分是多少 ##

**时间限制: **1 Sec

**内存限制: **32 MB

**提交: **313

**解决: **71

[提交][Link 1] [状态][Link 2]

### 题目描述 ###

老师想知道从某某同学到某某同学当中，分数最高的是多少。  
现在请你编程模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。

### 输入 ###

输入包含多组测试数据。  
每组输入第一行是两个正整数N和M（0<N<=30000,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。

### 输出 ###

对于每一次询问操作，在一行里面输出最高成绩。

### 样例输入 ###

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

### 样例输出 ###

### 提示 ###

线段树不解释！

#include<cstdio>
    #include<algorithm>
    using namespace std;
    #define lson l,m,rt<<1
    #define rson m+1,r,rt<<1|1//相当于(rt>>1)+1
    const int maxn=30010;
    int MAX[maxn<<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 sc,int l,int r,int rt)
    {
        if(l==r)
        {
            MAX[rt]=sc;
            return;
        }
        int m=(l+r)>>1;
        if(p<=m)
        {
            update(p,sc,lson);
        }
        else
        {
            update(p,sc,rson);
        }
        pushup(rt);
    }
    int query(int L,int R,int l,int r,int rt)
    {
        int p1,p2;
        if(l>R||r<L)
        {
            return -1;
        }
        if(L<=l&&r<=R)
        {
            return MAX[rt];
        }
         int m=(l+r)>>1;
        p1=query(L,R,lson);
        p2=query(L,R,rson);
        if(p1==-1)
        {
            return p2;
        }
        if(p2==-1)
        {
            return p1;
        }
        return max(p1,p2);
    }
    int main()
    {
        int n,m,a,b;
        char c[20];
        while(scanf("%d%d",&n,&m)!=EOF)
        {
            build(1,n,1);
            while(m--)
            {
                scanf("%s%d%d",&c,&a,&b);
                if(c[0]=='Q')
                {
                    printf("%d\n",query(a,b,1,n,1));
                }
                else
                {
                    update(a,b,1,n,1);
                }
            }
        }
    }

[Link 1]: http://arena.acmclub.com/submitpage.php?id=1111
[Link 2]: http://arena.acmclub.com/problemstatus.php?id=1111