数列区间最大值（MQR） ST表

数列区间最大值输入一串数字给你 M 个询问每次询问就给你两个数字 X,Y要求你说出 X 到 Y 这段区间内的最大数。输入格式第一行两个整数 N,M 表示数字的个数和要询问的次数接下来一行为 N 个数接下来 M 行每行都有两个整数 X,Y。输出格式输出共 M 行每行输出一个数。数据范围1≤N≤105,1≤M≤106,1≤X≤Y≤N,数列中的数字均不超过231−1输入样例10 2 3 2 4 5 6 8 1 2 9 7 1 4 3 8输出样例5 8import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; public class Main { static int N100010,mod998244353; static int a[]new int[N]; static int log2[]new int[N]; static BufferedReader br new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer stnew StringTokenizer(br.readLine()); int nInteger.parseInt(st.nextToken()),mInteger.parseInt(st.nextToken()); stnew StringTokenizer(br.readLine()); for (int i 1; i n; i) { a[i]Integer.parseInt(st.nextToken()); } //f(i,j) 表示以 i 为起点长度为 2^j 的区间的最大值 //依据倍增思想递推式 //f(i,j) max(f{i,j-1},f{i2^{j-1},j-1}) //因为f{i,j-1}区间为 [i,i2^{j-1}-1] f{i2^{j-1},j-1}区间为[i2^{j-1},i2^{j-1}2^{j-1}-1] //f{i2^{j-1},j-1}区间为[i2^{j-1},i2^{j-1}2^{j-1}-1] 也就是[i2^{j-1},i2^{j}-1] //f(i,j)区间为[i,i2^{j}-1] 即证 log2[1]0; for (int i 2; i N; i) { log2[i]log2[i1]1; } int f[][]new int[n1][log2[n1]1]; for (int j 0; (1j) n; j) {//要先j 再i for (int i 0; i (1(j))-1 n; i) { if(j0)f[i][j]a[i]; else f[i][j]Math.max(f[i][j-1], f[i(1(j-1))][j-1]); } } for (int i 0; i m; i) { stnew StringTokenizer(br.readLine()); int lInteger.parseInt(st.nextToken()),rInteger.parseInt(st.nextToken()); int klog2[r-l1]; //[l,l2^{k}-1] [r-2^{k}1,r] bw.write(Math.max(f[l][k], f[r-(1k)1][k])\n); } br.close(); bw.flush(); bw.close(); } }