当前位置:网站首页>ST表和区间最值
ST表和区间最值
2022-08-11 11:34:00 【Here_SDUT】
ST表
ST表可以通过 O(nlogn) 的预处理然后在 O(1) 的时间内算出某段区间的最值,空间复杂度也为 O(nlogn)。原理是利用了倍增和动态规划的思想,设 dp[i][j] 表示从第 i 个数开始的 2^j 个数的最值,状态转移为:dp[i][j] = max(dp[i][j-1],dp[i + (2^{j-1})][j-1]),若求最小值则用 min ,即将长度为 2^j 的区间对半分为两个长度为 2^{j-1} 的两个小区间,分别求最值 。由于要用到log运算,介绍一种 log_2 的预处理方法:
lg[0] = -1;
for(int i = 1; i <= n; i++) lg[i] = lo[i>>1]+1;
那么,可以写出ST表的预处理函数:
int a[maxn];//需要求最值的数组,以求最大值为例
void build(int n) {
for(int i = 1; i <= n; i++) dp[i][0] = a[i];//自己一个数时的最值就是自己
int lim = lg[n];//求出最大的lim使得 2 ^ lim <= n
for(int j = 1; j <= lim; j++)
for(int i = 1; i <= n - (1 << j) + 1; i++)
dp[i][j] = max(dp[i][j-1],dp[i + (1<<(j-1))][j-1]);
}
如果我们要求某个区间 L 到 R 的最大值,我们先找到最大的 k 使得 2^k \le r-l+1 \le 2^{k+1} ,那么区间的最大值 mx = max(dp[l][k],dp[r – (1<<k) + 1][k])2^k 的最大值和 以 R 结束的长度为 2^k 的最大值中取最大值,由于是取最值,所以区间重叠没有影响,函数为:
int cal1(int l, int r) {
int k = lg[r - l + 1];
return max(dp2[l][k], dp2[r - (1 << k) + 1][k]);
}
区间最值的一个性质
King of Range(2021牛客暑期多校训练营5 K题)
题意
给你1e5个数,求这些数组成的数列中,有多少对区间满足最大值和最小值的差小于 k。
分析
对于一个区间来说,如果将左边界向右移动,那么最大值只会不变或者变小,最小值只会不变或者变小;将右边界向右移动,最大值只会不变或者变大,最小值只会不变或者变小。所以,如果确定左边界 L 后,找到最小的右边界 R 满足题目要求,那么对于所有的以 L 为左端点和R右边任意一个点为右端点的区间都是满足题目要求的。于是我们可以从1开始枚举每个左端点,然后找到它最小的右端点,然后累加答案即可。由于左端点从左向右枚举,那么最大值只能变小,最小值只能变大,即使得情况更加不满足题目要求,倘若将右端点再向左移动,情况会更加不满足题目要求,所以右端点只可能向右移动不可能回头,故算法是 O(n) 的,但是当左端点向右移动后,不知道此刻的最小值和最大值为多少,可以用ST表预处理然后 O(1) 计算最值,故整体复杂度为 O(nlogn)。
代码
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
int a[maxn], dp1[maxn][50], dp2[maxn][50];
int mp[maxn];
int cal1(int l, int r) {
int k = mp[r - l + 1];
return max(dp2[l][k], dp2[r - (1 << k) + 1][k]);
}
int cal2(int l, int r) {
int k = mp[r - l + 1];
return min(dp1[l][k], dp1[r - (1 << k) + 1][k]);
}
int main(int argc, char const *argv[]) {
int n, m;
cin >> n >> m;
mp[0] = -1;
for(int i = 1; i <= n; i++) mp[i] = mp[i>>1]+1;
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
int lim = mp[n];
for (int i = 1; i <= n; i++) dp1[i][0] = dp2[i][0] = a[i];
for (int j = 1; j <= lim; j++) {
for (int i = 1; i <= n - (1 << j) + 1; i++) {
dp1[i][j] = min(dp1[i][j - 1], dp1[i + (1 << (j - 1))][j - 1]);
dp2[i][j] = max(dp2[i][j - 1], dp2[i + (1 << (j - 1))][j - 1]);
}
}
while (m--) {
int k;
cin >> k;
int r = 1;
LL ans = 0;
for (int l = 1; l <= n; l++) {
int ma = cal1(l, r), mi = cal2(l, r);
while (r < n && ma - mi <= k) {
r++;
if (a[r] > ma) ma = a[r];
if (a[r] < mi) mi = a[r];
}
// printf("%d %d %d\n",l, r, cal(l,r));
if (ma - mi > k)
ans += (n - r + 1);
else
break;
}
printf("%lld\n", ans);
}
return 0;
}
边栏推荐
猜你喜欢
CCF大会腾源会专场即将召开,聚焦基础软件与开发语言未来发展
EXCLUSIVE INTERVIEW | INTELLIGENCE IS SPONTANED, NOT PLANNED: Evolution Fan, Former OpenAI Research Manager and UBC Associate Professor Jeff Clune
如何用100元制作一块全志V853的AI 开发板
App Clip 苹果小程序开发须知
C语言,怪题小谈
《长津湖》和《三十而已》,不及王一博赚钱?
通过热透镜聚焦不同类型的高斯模式
或命名“狙击手” 长安全新皮卡申报图
蚂蚁集团开源密码学基础库 BabaSSL 正式更名“铜锁”
2022 OceanBase 年度发布会:发布四大策略,迈入4.0时代
随机推荐
Ince-Gaussian mode
C语言,怪题小谈
图像识别(八)| 还对全连接层迷迷糊糊?背会一首诗就行了
开源汇智创未来 | 软通动力出席开放原子全球开源峰会OpenAtom openEuler分论坛
Visual Studio: Arm64EC官方支持来了
挑战52天背完小猪佩奇(第02天)
Starting from zero configuration vim (11) -- plug-in management
Neural network visualization has 3 d version of the, the United States to fall!(open source)
TX12 + ExpressLRS 915MHz RC控制链路配置及问题汇总
pip安装后仍有ImportError No module named XX问题解决
六、一起学习Lua 循环
Typora表格中常用操作
威佐夫博弈
openEuler小程序会议指南
目标检测学习笔记——小目标检测
那些不用写代码也能做游戏的工具
黑马瑞吉外卖之分类信息的分页查询
五、一起学习Lua 变量
Uber的20万容器实践:如何避免容器化环境中的 CPU 节流
TX12 + ExpressLRS RC configuration and control link problem summary 915 MHZ