RMQ小结

2024-05-03 19:32
文章标签 小结 rmq

本文主要是介绍RMQ小结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

                                  RMQ小结

区间求值得算法主要有三种：

一、处理O（N），查询O（N*Q）   (朴素)

二、处理O(log N),查询（QlogN） (线段树)

三、处理O(nlogn),查询（1）    （RMQ）

而我们主要来讲一下，O(nlogn)-O(1)的RMQ算法。而RMQ算法的实现又有多种算法，我就选了一种性价比最高的讲解。就是代码容易，时间也可以的算法。因为正宗的RMQ的时间是O(N)-O(1)，我主要说的是ST算法O(NlogN)-O(1)的算法。

RMQ的本质思想是动态规划。度娘如是解释：

ST算法（Sparse Table），以求最大值为例，设d[i,j]表示[i,i+2^j-1]这个区间内的最大值，那么在询问到[a,b]区间的最大值时答案就是max(d[a,k], d[b-2^k+1,k])，其中k是满足2^k<=b-a+1(即长度)的最大的k,即k=[ln(b-a+1)/ln(2)]。
d的求法可以用动态规划，d[i, j]=max(d[i, j-1],d[i+2^(j-1), j-1])。

看一下ST算法是怎么实现的（以最大值为例）：
   首先是预处理，用一个DP解决。设a是要求 区间 最值的 数列 ，f[i,j]表示从第i个数起连续2^j个数中的最大值。例如数列3 2 4 5 6 8 1 2 9 7 ,f[1,0]表示第1个数起，长度为2^0=1的最大值，其实就是3这个数。f[1,2]=5，f[1,3]=8，f[2,0]=2，f[2,1]=4……从这里可以看出f[i,0]其实就等于a[i]。这样，DP的状态、初值都已经有了，剩下的就是 状态转移方程 。我们把f[i,j]（j≥1）平均分成两段（因为j≥1时，f[i,j]一定是偶数个数字），从i到i+2^(j-1)-1为一段，i+2^(j-1)到i+2^j-1为一段（长度都为2^（j-1））。用上例说明，当i=1，j=3时就是3,2,4,5 和6,8,1,2这两段。f就是这两段的最大值中的最大值。于是我们得到了动规方程F[i,j]=max(F[i,j-1],F[i+2^(j-1),j-1])。
接下来是得出最值，也许你想不到计算出f有什么用处，一般要想计算max还是要O(logn)，甚至O(n)。但有一个很好的办法，做到了O(1)。还是分开来。如在上例中我们要求区间[2,8]的最大值，就要把它分成[2,5]和[5,8]两个区间，因为这两个区间的最大值我们可以直接由f[2,2]和f[5,2]得到。扩展到一般情况，就是把区间[l,r]分成两个长度为2^n的区间（保证有f对应）。直接给出表达式：
k:=trunc(ln(r-l+1)/ln(2));
ans:=max(F[l,k],F[r-2^k+1,k]);
这样就计算了从l开始，长度为2^k的区间和从r-2^k+1开始长度为2^k的区间的最大值（表达式比较繁琐，细节问题如加1减1需要仔细考虑），二者中的较大者就是整个区间[l,r]上的最大值。 

#include <iostream>
#include <cstdio>
#include <cmath>
#include<algorithm>
#define MN 50005
using namespace std;
int mi[MN][17],mx[MN][17],w[MN];
int n,q;
void rmqinit()
{int i,j,m;for(i=1;i<=n;i++){mi[i][0]=mx[i][0]=w[i];}int m = int(trunc(log2(n)));for(i=1;i<=m;i++){for(j=n;j>=1;j--){mx[j][i]=mx[j][i-1];if(j+(1<<(i-1))<=n)mx[j][i]=max(mx[j][i],mx[j+(1<<(i-1))][i-1]);mi[j][i]=mi[j][i-1];if(j+(1<<(i-1)<=n))mi[j][i]=min(mi[j][i],mi[j+(1<<(i-1))][i-1]);}}
}int rmqmin(int l,int r)
{int m=int(trunc(log2(r-l+1)));return min(mi[l][m],mi[r-(1<<m)+1][m]);
}int rmqmax(int l,int r)
{int m=int(trunc(log2(r-l+1)));return max(mx[l][m],mx[r-(1<<m)+1][m]);
}int main()
{cin>>n>>q;for(int i=1;i<=n;i++)scanf("%d",&w[i]);//cin>>w[i];rmqinit();int l,r;for(int i=1;i<=q;i++){scanf("%d%d",&l,&r);//cin>>l>>r;printf("%d %d\n",rmqmax(l,r),rmqmin(l,r));//cout<<rmqmax(l,r)<<" "<<rmqmin(l,r)<<endl;}while(cin>>n)return 0;
}




练练手.HDU3486
题目链接： Click Here~

题目分析：
题目重述，题目说给出一个老板要面试N个人，且这N个人，每个人都有自己的能力值。但是他没有那么多的时间。因此，他决定将这N个人按原来报道的顺序将他们分成m组。而剩下的人由于来的晚，所以，就直接不给他们面试的机会了。题目问，分别从m组中挑选出N/m个人。且boss希望员工在m组中每组的最高能力值的总和不小于k。而要你求出至少要分成几组？

算法分析：
朴素的算法，求出组数是从1~N的遍历，在求出这1~N组中每组的人的最大能力值。这明显超时。但是哪里可以优化呢？我们发现程序中只有两处核心；一，求组数。二，求每组中人的最大能力值。只要解决了这个两个问题，当然就可以解决了超时的问题。
如何，优化组数呢？我们可以想最好的情况是没跟人的能力值都一样的，那么此时就是组数的下界。那么，我们就可以求出N个人中最大能力值（maxv）是多少。而最小组数就是k/maxv了（想想为什么？）而上界就是N组.‘
如何，优化每组中人的最大能力值呢？显然就是我们开篇讲的RMQ.

然后呢，这道题的数据有问题。可以用二分，但是本质上着N个人的能力值并不存在任何关系，因此根本就不能用二分。还有题目描述也很恶心。到底是保证组数最小呢？还是人数最小呢？这要自己猜吗？Are you kidding me? 

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;const int N = 2e5 + 5;
int n,dp[N][20];void RMQ_init()
{int m = int(trunc(log2(n)));
//    int m = (int)(log10(n*1.0)/log10(2.0));for(int j = 1;j <= m;++j)for(int i = 1;i+(1<<j)-1 <= n;i++)dp[i][j] = max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}
int RMQ(int L,int R)
{
//    int k = (int)(log10(R-L+1)*1.0/log10(2.0));int k = int(trunc(log2(R-L+1)));return max(dp[L][k],dp[R-(1<<k)+1][k]);
}
int main()
{int k;while(scanf("%d%d",&n,&k),(n>=0&&k>=0)){int sum = 0,maxv = 0;for(int i = 1;i <= n;++i){scanf("%d",&dp[i][0]);sum += dp[i][0];maxv = max(maxv,dp[i][0]);}if(sum <= k){puts("-1");continue;}RMQ_init();int ans = n,st = k/maxv;if(!st) st++; //注意出现除0的情况---->Runtime Error!!!!!!!!!!!!!!for(int i = st;i < n;++i)  //枚举组数{int seg,s = 0;seg = n/i;            //可以分成几个区间for(int j = 1;j <= i;j++) //在i个区间内,各个区间的起点和终点{s += RMQ((j-1)*seg+1,j*seg);if(s > k)break;}if(s > k){ans = i;break;}}printf("%d\n",ans);}return 0;
}





                         AMagic Lamp



题目链接：Click Here~

题意解析：

    题目要求，给出一个字符串。让你在删除m个字符之后，求剩下的数组成的最小数是多少。(同理，求剩下的数组成的最大数也是同样的解法)

思路解析：

显然，要删除m个数则原字符串比剩下n-m个（原字符串长度为n）.则，我们知道当两个数的位数相同的时候，就要比较他的首位。

比如，1999与2000.因此，我们要尽量的使首位变小。而这只要在一个区间中找出最小的那个就好了。而问题有出现了，要怎么确定去区间呢？显然，我们在找第一位的时候，后面肯定要至少剩下n-m-1个数。且我们假设我们找到的第一位索引为i1。则第二位的区间可以很容易的确定是从i+1为起点后面至少剩下n-m-2个的区间内。同理，后面的都是相同的道理。

    而我们知道区间求极值，我们又可以使用RMQ求得最值。而当运用RMQ的时候我们又可以从逆向思维来考虑。当我们找第一位的时候既然后面要剩下n-m-1个，那不是说明第一位的最值一定是在[0,m]内，第二个在[i1,m+1]呢,ect？这是显然的。所以，我们可以轻松的运用RMQ求出每个区间的最值是多少。



#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;const int N = 1e3 + 5;
int n,pos[N][20];
char str[N];
void RMQ_init()
{for(int i = 0;i <= n;++i) pos[i][0] = i;int m = int(trunc(log2(n)));for(int j = 1;j <= m;++j)for(int i = 0;i +(1<<j)-1 <= n;++i){int s1 = pos[i][j-1];int s2 = pos[i+(1<<(j-1))][j-1];pos[i][j] = str[s1]<=str[s2]?s1:s2;}
}
int RMQ(int L,int R)
{int m = int(trunc(log2(R-L+1)));int s1 = pos[L][m];int s2 = pos[R-(1<<m)+1][m];return str[s1] <= str[s2]?s1:s2;
}
int main()
{int m;while(~scanf("%s%d",str,&m)){n = strlen(str); // printf("str ---> %s   n -- > %d\n",str,n);RMQ_init();
//        char res[N];bool first = true;int index,idx = 0,j = m;
//        memset(res,'\0',sizeof(res));for(int i = 1;i <= n-m;++i){index = RMQ(idx,j);j++;if(first&&str[index]!='0'){first = false;putchar(str[index]);}else if(!first){putchar(str[index]);}idx = index+1;}if(first) putchar('0');putchar('\n');}return 0;
}

 

Max Sum of Max-K-sub-sequence


     也可以运用单调队列。Click Here~




                                




这篇关于RMQ小结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/957475。

相关文章

Redis分片集群、数据读写规则问题小结

Redis分片集群、数据读写规则问题小结

《Redis分片集群、数据读写规则问题小结》本文介绍了Redis分片集群的原理,通过数据分片和哈希槽机制解决单机内存限制与写瓶颈问题,实现分布式存储和高并发处理,但存在通信开销大、维护复杂及对事务支持... 目录一、分片集群解android决的问题二、分片集群图解 分片集群特征如何解决的上述问题？（与哨兵模
阅读更多...
SpringBoot中使用Flux实现流式返回的方法小结

SpringBoot中使用Flux实现流式返回的方法小结

《SpringBoot中使用Flux实现流式返回的方法小结》文章介绍流式返回（StreamingResponse）在SpringBoot中通过Flux实现,优势包括提升用户体验、降低内存消耗、支持长连... 目录背景流式返回的核心概念与优势1. 提升用户体验2. 降低内存消耗3. 支持长连接与实时通信在Sp
阅读更多...
Python打印对象所有属性和值的方法小结

Python打印对象所有属性和值的方法小结

《Python打印对象所有属性和值的方法小结》在Python开发过程中,调试代码时经常需要查看对象的当前状态,也就是对象的所有属性和对应的值,然而,Python并没有像PHP的print_r那样直接提... 目录python中打印对象所有属性和值的方法实现步骤1. 使用vars()和pprint()2. 使
阅读更多...
HTML5 getUserMedia API网页录音实现指南示例小结

HTML5 getUserMedia API网页录音实现指南示例小结

《HTML5getUserMediaAPI网页录音实现指南示例小结》本教程将指导你如何利用这一API，结合WebAudioAPI，实现网页录音功能,从获取音频流到处理和保存录音，整个过程将逐步... 目录1. html5 getUserMedia API简介1.1 API概念与历史1.2 功能与优势1.3
阅读更多...
Java对异常的认识与异常的处理小结

Java对异常的认识与异常的处理小结

《Java对异常的认识与异常的处理小结》Java程序在运行时可能出现的错误或非正常情况称为异常,下面给大家介绍Java对异常的认识与异常的处理,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参... 目录一、认识异常与异常类型。二、异常的处理三、总结 一、认识异常与异常类型。（1）简单定义-什么是
阅读更多...
Python函数返回多个值的多种方法小结

Python函数返回多个值的多种方法小结

《Python函数返回多个值的多种方法小结》在Python中,函数通常用于封装一段代码,使其可以重复调用,有时,我们希望一个函数能够返回多个值,Python提供了几种不同的方法来实现这一点,需要的朋友... 目录一、使用元组（Tuple）:二、使用列表（list）三、使用字典（Dictionary）四、 使
阅读更多...
Python程序的文件头部声明小结

Python程序的文件头部声明小结

《Python程序的文件头部声明小结》在Python文件的顶部声明编码通常是必须的,尤其是在处理非ASCII字符时,下面就来介绍一下两种头部文件声明,具有一定的参考价值,感兴趣的可以了解一下... 目录一、# coding=utf-8二、#!/usr/bin/env python三、运行Python程序四、
阅读更多...
Python中合并列表(list)的六种方法小结

Python中合并列表(list)的六种方法小结

《Python中合并列表(list)的六种方法小结》本文主要介绍了Python中合并列表(list)的六种方法小结,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋... 目录一、直接用 + 合并列表二、用 extend() js方法三、用 zip() 函数交叉合并四、用
阅读更多...
Spring Boot中的YML配置列表及应用小结

Spring Boot中的YML配置列表及应用小结

《SpringBoot中的YML配置列表及应用小结》在SpringBoot中使用YAML进行列表的配置不仅简洁明了,还能提高代码的可读性和可维护性,：本文主要介绍SpringBoot中的YML配... 目录YAML列表的基础语法在Spring Boot中的应用从YAML读取列表列表中的复杂对象其他注意事项总
阅读更多...
CSS 样式表的四种应用方式及css注释的应用小结

CSS 样式表的四种应用方式及css注释的应用小结

《CSS样式表的四种应用方式及css注释的应用小结》：本文主要介绍了CSS样式表的四种应用方式及css注释的应用小结，本文通过实例代码给大家介绍的非常详细，详细内容请阅读本文，希望能对你有所帮助... 一、外部 css（推荐方式）定义：将 CSS 代码保存为独立的 .css 文件，通过 <link> 标签
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2