题解 | #最高分是多少#

使用线段树的Java题解。

需要注意两个细节：

1. 题目中说明输入有多组测试数据
2. 两个整数A和B之间的大小顺序需要考虑，如果"A>B"，则需要先调换位置。
   

代码如下：

import java.util.Scanner;

class SegmentTree {

    private int[] data;
    private int[] nodes;
    private int len;

    public SegmentTree(int[] data) {
        this.data = data;
        this.len = data.length;
        this.nodes = new int[this.len << 2];
        this.build(1, 1, data.length);
    }

    private void build(int idx, int l, int r) {
        if (l == r) {
            this.nodes[idx] = this.data[l - 1];
            return;
        }

        int mid = (l + r) >> 1;
        this.build(idx << 1, l, mid);
        this.build(idx << 1 | 1, mid + 1, r);
        this.nodes[idx] = Math.max(this.nodes[idx << 1], this.nodes[idx << 1 | 1]);
    }

    public void update(int tIdx, int tVal) {
        if (tIdx <= 0 || tIdx > this.len) {
            return;
        }
        this._update(tIdx, tVal, 1, 1, this.len);
    }

    private void _update(int tIdx, int tVal, int idx, int l, int r) {
        if (l == r) {
            this.nodes[idx] = tVal;
            return;
        }

        int mid = (l + r) >> 1;
        if (tIdx <= mid) {
            this._update(tIdx, tVal, idx << 1, l, mid);
        } else {
            this._update(tIdx, tVal, idx << 1 | 1, mid + 1, r);
        }
        this.nodes[idx] = Math.max(this.nodes[idx << 1], this.nodes[idx << 1 | 1]);
    }

    public int query(int L, int R) {
        if (L > R) {
            int temp = L;
            L = R;
            R = temp;
        }
        if (L <= 0  || R > this.len) {
            return -1;
        }
        return this._query(L, R, 1, 1, this.len);
    }

    private int _query(int L, int R, int idx, int l, int r) {
        if (L == l && R == r) {
            return this.nodes[idx];
        }

        int mid = (l + r) >> 1;
        if (R <= mid) {
            return this._query(L, R, idx << 1, l, mid);
        } else if (L > mid) {
            return this._query(L, R, idx << 1 | 1, mid + 1, r);
        } else {
            return Math.max(this._query(L, mid, idx << 1, l, mid), this._query(mid + 1, R, idx << 1 | 1, mid + 1, r));
        }
    }

}

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        while (scanner.hasNext()) {
            int N = scanner.nextInt();
            int M = scanner.nextInt();

            int[] data = new int[N];
            for (int i = 0; i < N; i++) {
                data[i] = scanner.nextInt();
            }


            SegmentTree maxTree = new SegmentTree(data);

            for(int i = 0; i < M; i++) {
                String oper = scanner.next();
                int L = scanner.nextInt();
                int R = scanner.nextInt();
                if ("Q".equals(oper)) {
                    System.out.println(maxTree.query(L, R));
                } else if ("U".equals(oper)) {
                    maxTree.update(L, R);
                }
            }
        }

        scanner.close();
    }

}