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)。 完整代码如下： [cpp] #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; } [/cpp] 代码中求pre_calc时需要注意二重循环的顺序不要搞反了，因为我们是先求得小区间的最小值才能求大区间的最小值，所以第一重循环应该是区间的长度，而不是区间的起点。 本代码提交AC，用时875MS，内存138MB。（用cin，cout超时。。。） 这篇文章介绍了用RMQ-ST算法求解区间最大值和最小值的方法。]]>