RMQ(log2储存方法)
2024-09-25 15:25:42
RMQ |
难度级别:B; 运行时间限制:1000ms; 运行空间限制:256000KB; 代码长度限制:2000000B |
试题描述 |
长度为n的数列A,以及q个询问,每次询问一段区间的最小值。 |
输入 |
第一行,一个整数n |
输出 |
针对每个询问,输出结果。每个结果占一行。 |
输入示例 |
5 |
输出示例 |
2 |
其他说明 |
数据规模:n, q, Ai<=100000 |
#include<iostream> #include<cmath> using namespace std; int f[][]; void rmq(int num) { for(int j=;j<;j++) for(int i=;i<=num;i++) if(i+(<<j)-<=num) f[i][j]=min(f[i][j-],f[i+(<<(j-))][j-]); } int main() { int i,j,n,t,m; scanf("%d",&n); for(i=;i<=n;i++) { scanf("%d",&f[i][]); } rmq(n); int s,p,maxl,minl; cin>>m; while(m--) { scanf("%d%d",&s,&p); int k=(int)((log(p-s+))/log(2.0)); minl=min(f[s][k],f[p-(<<k)+][k]); printf("%d\n",minl); } }
最新文章
- Jcapta
- 关于 app测试工具
- Winform 换皮肤
- IOS 中关于自定义Cell 上的按钮 开关等点击事件的实现方法(代理)
- 【JavaScript】Object.prototype.toString.call()进行类型判断
- Javascript中的async await
- 个人作业2—英语学习APP案例分析
- 在 Vim 中设置 Tab 为4个空格
- Powerdesigner逆向工程64位Oracle数据库
- macOS Mojave待机耗电大
- PBRT笔记(4)——颜色和辐射度
- 【Spring学习】【Java基础回顾-数据类型】
- 从零开始搭建django前后端分离项目 系列二(项目搭建)
- 【转】Java内部类详解
- 点评qq浏览器
- 7、Python-引用传递与值传递
- 使用Bootstrap Popover实现一个弹框上三角形的代码记录
- vue 开发系列(七) 路由配置
- 团队作业——Beta冲刺2
- 在容器服务kubernetes上配置https