数列区间最大值（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(); } }

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

相关推荐

QrazyBox：二维码修复终极指南 - 从损坏到解码的完整解决方案

Dartmouth 的 AI 导师实验：0.71 到 1.30 个标准差，到底意味着什么

基于multisim的低频信号发生及处理系统电路设计

更多资讯

Linux下Oracle 11gR2单实例安装与避坑全流程

E-R图转关系模式实战与数据库设计全流程

MySQL线程池高并发压测：从TPS到stall_limit

RSIAgent：让智能体在新环境中递归自我进化的工程实践

空间智能平台：城市治理的数字孪生实践

Oracle EBS ASCP高级供应链计划实战：多工厂手机制造案例配置与验收

今日更新

AI辅助技术栈评估：提升研发决策效率60%

从生成Token到直接决策：Jev如何重塑AI Agent工程实践

32G统一内存跑大模型：内存账、TPS实测与端云分流

本周精选

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？