算法分析

线段树

• 将动态求连续区间和线段树中的sum改为Max即可

注意:由于此题的输入输出过大，需要用BufferedReader，和BufferedWriter输入输出，血的教训

时间复杂度 $O(nlogn)$

参考文献

蓝桥杯辅导课

Java 代码

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    static int N = 100010;
    static int[] w = new int[N];
    static Node[] tr = new Node[N * 4];
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static void build(int u,int l,int r)
    {
        if(l == r) tr[u] = new Node(l,r,w[r]);
        else
        {
            tr[u] = new Node(l,r,Integer.MIN_VALUE);
            int mid = l + r >> 1;
            build(u << 1,l,mid);
            build(u << 1 | 1,mid + 1,r);
            tr[u].maxv = Math.max(tr[u << 1].maxv,tr[u << 1 | 1].maxv);
        }
    }
    static int query(int u,int l,int r)
    {
        if(tr[u].l >= l && tr[u].r <= r) return tr[u].maxv;
        int mid = tr[u].l + tr[u].r >> 1;
        int maxv = Integer.MIN_VALUE;
        if(l <= mid) maxv = query(u << 1,l,r);
        if(r > mid) maxv = Math.max(maxv, query(u << 1 | 1,l,r));
        return maxv;
    }
    public static void main(String[] args) throws IOException {
        String[] s1 = br.readLine().split(" ");
        int n = Integer.parseInt(s1[0]);
        int m = Integer.parseInt(s1[1]);
        String[] s2 = br.readLine().split(" ");
        for(int i = 1;i <= n;i++) w[i] = Integer.parseInt(s2[i - 1]);
        build(1,1,n);
        while(m -- > 0)
        {
            String[] s3 = br.readLine().split(" ");
            int l = Integer.parseInt(s3[0]);
            int r = Integer.parseInt(s3[1]);
            bw.write(query(1, l, r) + "\n");
        }
        bw.close();
    }
}
class Node
{
    public int l;
    public int r;
    public int maxv;
    public Node(int l,int r,int maxv)
    {
        this.l = l;
        this.r = r;
        this.maxv = maxv;
    }
}