最高分是多少

（java实现）

题目描述：

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

输入描述：

输入包括多组测试数据。
每组输入第一行是两个正整数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。

输出描述：

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

示例1：

输入

5 7
1 2 3 4 5
Q 1 5
U 3 6
Q 3 4
Q 4 5
U 4 5
U 2 9
Q 1 5

输出

5
6
5
9

问题分析：

思路一：暴力法。每次查询直接做。
修改复杂度O(1)，查询复杂度O(N)
思路二：使用线段树。线段树这种数据结构，修改O(logn)，查询O(logn)，但是要预处理O(nlogn)

相关知识：

参考代码：

思路一实现：

import java.util.*;
public class Main {
    public static void main(String[] args)
    {
        Scanner input = new Scanner(System.in);
        while (input.hasNext())
        {
            String[] str = input.nextLine().split(" ");
            int n = Integer.parseInt(str[0]);
            int m = Integer.parseInt(str[1]);
            int[] arr = new int[n+1];
            str = input.nextLine().split(" ");
            for (int i=1; i<=n; i++)
            {
                arr[i] = Integer.parseInt(str[i-1]);
            }
            for (int i=0; i<m; i++)
            {
                str = input.nextLine().split(" ");
                int index = Integer.parseInt(str[1]);
                int value = Integer.parseInt(str[2]);
                if (str[0].equals("Q"))
                {
                    System.out.println(getMax(arr,index,value));
                }else if (str[0].equals("U"))
                {
                    arr[index] = value;
                }
            }
        }
    }
    public static int getMax(int[] arr, int a, int b)
    {
        int max = Integer.MIN_VALUE;
        // a不一定是最小的
        if (a > b)
        {
            int tmp = a;
            a = b;
            b = tmp;
        }
        for (int i=a; i<=b; i++)
        {
            if (max < arr[i])
                max = arr[i];
        }
        return max;
    }
}

思路一实现：（不使用nextLine()）;

import java.util.Scanner;
public class Main {

     public static void main(String[] args)throws Exception{
        Scanner s = new Scanner(System.in);
        while(s.hasNext())
        {
            int n = s.nextInt();
            int m = s.nextInt();
            int[] arr = new int[n];
            for(int i = 0; i <n; i ++)
            {
                arr[i] = s.nextInt();
            }
            int count = 0;
            char a ;
            int b,c;
            while(count < m)
            {
                a = s.next().charAt(0);
                b = s.nextInt();
                c = s.nextInt();
                if('Q' == a)
                {
                    int start, end;
                    if(b <= c)
                    {
                        start = b - 1;
                        end = c - 1;
                    }else{
                        start = c - 1;
                        end = b - 1;
                    }
                    int max = arr[start];
                    for(int index=start; index<=end; index++)
                    {
                        if(arr[index] > max)
                            max = arr[index];
                    }
                    System.out.println(max);
                }
                if('U' == a){
                    int index1 = b - 1;
                    int newValue = c;
                    arr[index1] = newValue;
                }
                s.nextLine();
                count++;
            }
         }
         s.close();
    }
}

思路二实现：

import java.util.Scanner;
public class Main {
    public static int MAXN=100000;
    public static int[] data = new int[MAXN+5];
    public static int[] maxarr = new int[MAXN*4+5];
    public static void main(String[] args)
    {
        Scanner input = new Scanner(System.in);
        while (input.hasNext())
        {
            String[] str = input.nextLine().split(" ");
            int n = Integer.parseInt(str[0]);
            int m = Integer.parseInt(str[1]);
            /*
            int n = input.nextInt();
            int m = input.nextInt();
            */
            str = input.nextLine().split(" ");
            for (int i=1; i<=n; i++)
            {
                data[i] = Integer.parseInt(str[i-1]);
            }
            /*
            for (int i=1; i<=n; i++)
            {
                data[i] = input.nextInt();
            }*/
            build(1, 1, n);
            char order;
            int a=0, b=0;
            for (int i=0; i<m; i++)
            {
                str = input.nextLine().split(" ");
                order = str[0].charAt(0);
                a = Integer.parseInt(str[1]);
                b = Integer.parseInt(str[2]);
                /*
                order = input.next().charAt(0);
                a = input.nextInt();
                b = input.nextInt();
                */
                if ('U' == order)
                {
                    update(a,b,1,1,n);
                }else if ('Q' == order)
                {
                    if (a>b)
                    {
                        int tmp = a;
                        a = b;
                        b = tmp;
                    }
                    System.out.println(querymax(a,b,1,1,n));
                }
                //input.nextLine();
            }

        }
    }

    public static void build(int p,int l,int r)
    {
        if (l == r)
        {
            maxarr[p] = data[l];
            return;
        }
        int m = (l+r)>>1;
        int lchild = p<<1, rchild = p<<1|1;
        build(lchild, l, m);
        build(rchild, m+1, r);
        maxarr[p] = Math.max(maxarr[lchild], maxarr[rchild]);
    }
    public static void update(int idx, int value, int p, int l, int r)
    {
        if (l==r && l==idx)
        {
            maxarr[p] = value;
            return;
        }
        int m = (l+r)>>1;
        if (idx <= m)
            update(idx, value, p<<1, l, m);
        if (m < idx)
            update(idx, value, p<<1|1, m+1, r);
        maxarr[p] = Math.max(maxarr[p<<1], maxarr[p<<1|1]);
    }
    public static int querymax(int L, int R, int p, int l, int r)
    {
        if (L<=l && r<=R)
            return maxarr[p];
        int m = (l+r)>>1;
        int lans=-1,rans=-1;
        if (L<=m)
            lans = querymax(L,R,p<<1,l,m);
        if (m < R)
            rans = querymax(L,R,p<<1|1,m+1,r);
        if (lans==-1)
            return rans;
        if (rans==-1)
            return lans;
        return Math.max(lans,rans);
    }
}