ST表略解
2024-08-27 16:04:20
题面
给定一个长度为\(N\)的数列,和\(M\)次询问,求出每一次询问的区间内数字的最大值。
对于30%的数据,满足: \(1≤N,M≤10\)
对于70%的数据,满足: \(1≤N,M≤10^5\)
对于100%的数据,满足: \(1≤N≤10^5,1≤M≤10^6,a_i∈[0,10^9],1≤li≤ri≤N\)
线段树裸体啊。
但是这道题目线段树明显过不去这道题。所以我们要另辟蹊径我们观察题目,题目并没有要求我们进行更改操作,所以st表就派上用场了。
前置要求
正文
如果你会上面的内容了,那么你可以开始学st表了
st表实际上就是一个倍增+dp
我们令\(f[i][j]\)为\([i,i+2^j-1]\)内的最大值
我们可以将\([i,i+2^j-1]\)分成两半,即\([i,i+2^{j-1}-1]\)和\([i+2^{j-1},i+2^j-1]\)
两段的长度都为\(2^j\)
于是我们可以写出转移方程f[i][j]=min(f[i][j-1],f[i+1<<(j-1)-1][j-1])
注意需要预处理一下\(f[i][0]\)的值
那么询问怎么办?
对于一段询问的区间\([l,r]\)
我们可以算出从l到r最少需要加上2的多少次方,即k=log(r-l+1)/log(2)
这里运用到了换底公式,也可以直接写成k=log2(r-l+1)
code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9') c=='-'?f=-1,c=getchar():c=getchar();
while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
return x*f;
}
int f[100001][21],a[100001],n=read(),m=read(),x,y;
void init(){
for(int i=1;i<=n;i++)
f[i][0]=a[i];
for(int j=1;j<19;j++)
for(int i=1;i+(1<<j)-1<=n;i++)
f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
int find(int x,int y){
int k=log(y-x+1)/log(2);
return max(f[x][k],f[y-(1<<k)+1][k]);
}
int main(){
for(int i=1;i<=n;i++)
a[i]=read();
init();
while(m--)
x=read(),y=read(),printf("%d\n",find(x,y));
return 0;
}
最新文章
- NOIP2016纪录[那些我所追求的]
- codevs 1052 地鼠游戏
- redis/php redis扩展 安装
- 【学习笔记】【C语言】逗号运算符
- poj3321
- Javascript实现Web颜色值转换
- Qt Creator下载
- IE WebDriver 因保护模式无法启动的解决 (转载)
- redis php sort 函数
- Alpha冲刺(10/10)
- docker报错:Failed to restart docker.service: Unit not found.
- System.out.println()和System.err.println()
- 推荐系统之协同过滤的原理及C++实现
- 排序NB三人组
- 简单实用UML关系图解
- Android中创建PopupMenu弹出式菜单
- windows快捷键补充?
- php中120个内置函数
- Python3基础 三元运算符 简单示例
- Oracle数据库基本操作(四) —— PLSQL编程
热门文章
- ubuntu 14.04使用root登陆出现错误“Error found when loading /root/.profile”解决
- 高并发场景下System.currentTimeMillis()的性能问题的优化 以及SnowFlakeIdWorker高性能ID生成器
- PLSQL Developer备份恢复oracle数据
- Lambda表达式中使用正则表达式
- webService调用模式比较
- Bootstrap 学习资料
- elasticsearch2.x线程池配置
- 【codevs2822】爱在心中
- ROS naviagtion analysis: costmap_2d--StaticLayer
- 关于box-sizing属性