ST函数(ST表)RMQ O(1)查询 离线
2024-08-23 13:34:08
ST算法是基于倍增的动态规划算法。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
using namespace std;
int map[1000005][20];
int N,K;
void work()
{
int i,j;
for(j=1;1<<j<=N;j++)
for(i=1;i+(1<<j)-1<=N;i++)//i+(1<<j)-1<=n是为了保证区间左端点不超出总数n
map[i][j]=min(map[i][j-1],map[i+(1<<j-1)][j-1]);//实质是动态规划
}
int question(int z,int y)
{
int x=int (log(y-z+1)/log(2));//注意y-z要加一才为区间长度
return min(map[z][x],map[y-(1<<x)+1][x]);//分别以左右两个端点为基础,向区间内跳1<<x的最
//大值;
}
int main()
{
scanf("%d",&N);//输入数据总数
scanf("%d",&K);//输入询问次数k
for(int i=1;i<=N;i++)
scanf("%d",&map[i][0]);//数据输入加初始化,即从i开始向右走2的0次方的区间中的最大值,(注//意i到i的长度为一)。
work();//预处理
for(int i=1;i<=K;i++)
{
int a,b;
scanf("%d%d",&a,&b);
printf("%d ",question(a,b));//输出结果
}
return 0;
}
最新文章
- vsftpd.conf 怎么保存
- jQuery Mobile学习日记(二)
- sql语句延时执行或者是指定时间执行
- POJ 1847 Tram【Floyd】
- (三)开始在OJ上添加签到功能
- mysql 内外链接
- Android开发_字符串处理类-TextUtils类
- SHDP--Working With HBase(一)之基本介绍
- 4.5	HOOK分发函数
- 静默获取微信用户openid如此简单,只需要一句话
- Centos下配置tomcat7的https证书
- CCF系列之数字排序(201503-2)
- 流API--流的收集
- PHP-max_execution_time与fpm.request_terminate_timeout介绍
- SQL Server 查询某个字段值在哪张表的哪个字段
- pandas Dataframe 取某行
- PAT 1028 人口普查
- 使用ServiceDesk Plus保证及时解决问题,防止违反SLA
- MySQL--常见ALTER TABLE 操作
- 网络I/O模型--06异步I/O