hihoCoder 1068-RMQ-ST算法

hihoCoder 1068-RMQ-ST算法

#1068 : RMQ-ST算法
时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述
小Hi和小Ho在美国旅行了相当长的一段时间之后,终于准备要回国啦!而在回国之前,他们准备去超市采购一些当地特产——比如汉堡(大雾)之类的回国。

但等到了超市之后,小Hi和小Ho发现者超市拥有的商品种类实在太多了——他们实在看不过来了!于是小Hi决定向小Ho委派一个任务:假设整个货架上从左到右拜访了N种商品,并且依次标号为1到N,每次小Hi都给出一段区间[L, R],小Ho要做的是选出标号在这个区间内的所有商品重量最轻的一种,并且告诉小Hi这个商品的重量,于是他们就可以毫不费劲的买上一大堆东西了——多么可悲的选择困难症患者。

(虽然说每次给出的区间仍然要小Hi来进行决定——但是小Hi最终机智的选择了使用随机数生成这些区间!但是为什么小Hi不直接使用随机数生成购物清单呢?——问那么多做什么!)

提示一:二分法是宇宙至强之法!(真的么?)

提示二:线段树不也是二分法么?

输入

每个测试点(输入文件)有且仅有一组测试数据。

每组测试数据的第1行为一个整数N,意义如前文所述。

每组测试数据的第2行为N个整数,分别描述每种商品的重量,其中第i个整数表示标号为i的商品的重量weight_i。

每组测试数据的第3行为一个整数Q,表示小Hi总共询问的次数。

每组测试数据的第N+4~N+Q+3行,每行分别描述一个询问,其中第N+i+3行为两个整数Li, Ri,表示小Hi询问的一个区间[Li, Ri]。

对于100%的数据,满足N<=10^6,Q<=10^6, 1<=Li<=Ri<=N,0<weight_i<=10^4。

输出

对于每组测试数据,对于每个小Hi的询问,按照在输入中出现的顺序,各输出一行,表示查询的结果:标号在区间[Li, Ri]中的所有商品中重量最轻的商品的重量。

样例输入
10
7334
1556
8286
1640
2699
4807
8068
981
4120
2179
5
3 4
2 8
2 4
6 8
7 10
样例输出
1640
981
1556
981
981


给出n个数字,连续q次问[l,r]区间的最小值是多少。如果每询问一次都用遍历的方式求最小值,则总的时间复杂度为O(nq)。

本题给出了一个新的算法--RMQ-ST算法,它的时间复杂度为O(nlogn+q),如果q很大,比如接近n时,RMQ-ST算法就有优势了。

RMQ-ST算法的基本思想是先计算某个小区间a的最小值,当需要计算大区间b的最小值时,把它分成两个小区间a1,a2,因为小区间的最小值之前已经计算出来了,也就是a1,a2已知,则b=min{a1,a2}。这样每次询问[l,r]区间的最小值时,我们也只需要把[l,r]分成两个[l,t]和[t+1,r]区间,取这两个区间最小值的最小值,这样的时间复杂度是O(1)。

所以关键就在于怎么求所有小区间的最小值。

根据提示,为了简便,我们只求2的幂的长度区间的最小值,设数组int pre_calc[i][j]为区间[i,i+2^j-1]的最小值(从i开始,长度为2^j的区间最小值),因为长度为1的区间的最小值就是其本身,所以有pre_calc[i][0]=weight[i]。

因为pre_calc[i][j]的长度为2^j,所以我们正好可以将其分成2个长度为2^(j-1)的区间,也就是说pre_calc[i][j]=min{pre_calc[i][j-1],pre[i+2^(j-1)][j-1]}。

这样我们就找到了pre_calc的递推公式(实质是DP里的状态转换方程),那么j的取值范围是怎样的呢?因为长度为n的数组其最大子区间长度就是n,所以j的最大值就是log(n),下面只需一个二重循环就可求解。

当来了一个询问[l,r]时,我们也需要将其分成两个长度为2的幂的子区间a和b,假设这个幂为t,为了使两个子区间完全覆盖[l,r],两个子区间甚至可以重叠,所以a的右边缘需要大于等于b的左边缘,即l+2^t>=r-2^t+1,得到t>=log(r-l+1)-1,所以我们可以取t=log(r-l+1)。

完整代码如下:

#include<stdio.h>
#include<math.h>
#define MAX_N 1000010
int n,q;
int weight[MAX_N];
int pre_calc[MAX_N][30];

//求a,b最小值
int get_min(int a,int b)
{
     return a<b?a:b;
}

//初始化
void init_pre()
{
     for(int j=1;j<=n;j++)
          pre_calc[j][0]=weight[j];

     int m=floor(log((double)n)/log(2.0));//指数最大值

     for(int i=1;i<=m;i++)
     {
          for(int j=n;j>0;j--)
          {
               pre_calc[j][i]=pre_calc[j][i-1];
               if(j+(1<<(i-1))<=n)//如果另一半也存在的话。//1<<(i-1)其实就是2^(i-1)
                    pre_calc[j][i]=get_min(pre_calc[j][i],pre_calc[j+(1<<(i-1))][i-1]);
          }
     }
}
int main()
{
     //freopen("input.txt","r",stdin);

     scanf("%d",&n);
     for(int i=1;i<=n;i++)
          scanf("%d",&weight[i]);

     init_pre();

     scanf("%d",&q);
     int l,r,t;
     while(q--)
     {
          scanf("%d%d",&l,&r);
          t=floor(log(double(r-l+1))/log(2.0));//找到能使[l,r]分为两半的指数
          printf("%d\n",get_min(pre_calc[l][t],pre_calc[r-(1<<t)+1][t]));
     }
     return 0;
}

代码中求pre_calc时需要注意二重循环的顺序不要搞反了,因为我们是先求得小区间的最小值才能求大区间的最小值,所以第一重循环应该是区间的长度,而不是区间的起点。

本代码提交AC,用时875MS,内存138MB。(用cin,cout超时。。。)

这篇文章介绍了用RMQ-ST算法求解区间最大值和最小值的方法。

2 thoughts on “hihoCoder 1068-RMQ-ST算法

  1. Pingback: hihoCoder 1069-最近公共祖先·三 | bitJoy > code

  2. Pingback: hihoCoder 1070-RMQ问题再临 | bitJoy > code

Leave a Reply

Your email address will not be published. Required fields are marked *