题目
1082 - Array Queries
Time Limit: 3 second(s) | Memory Limit: 64 MB |
Given an array with N elements, indexed from 1 to
N. Now you will be given some queries in the form I J, your task is to find the minimum value from index
I to J.
Input
Input starts with an integer T (≤ 5), denoting the number of test cases.
The first line of a case is a blank line. The next line contains two integers
N (1 ≤ N ≤ 105), q (1 ≤ q ≤ 50000). The next line contains
N space separated integers forming the array. There integers range in
[0, 105].
The next q lines will contain a query which is in the form
I J (1 ≤ I ≤ J ≤ N).
Output
For each test case, print the case number in a single line. Then for each query you have to print a line containing the minimum value between index
I and J.
Sample Input |
Output for Sample Input |
2
5 3 78 1 22 12 3 1 2 3 5 4 4
1 1 10 1 1 |
Case 1: 1 3 12 Case 2: 10 |
Note
Dataset is huge. Use faster I/O methods.
题解
裸题,直接用ST表就可以过了。当然还是介绍下ST表的好。
RMQ问题,Range Minimum/Maximum Query,要求在一个有n个元素的数组中,支持查询操作,Query(L,R),计算这个区间内的最值。常用的算法是Tarjan的Spares-Table,也就是我们介绍的ST表,这个算法优化方式是“空间换时间”,核心是“二分”,预处理的时间复杂度为O(nlogn),查询的时间复杂度是O(1),总的空间复杂度是O(nlogn)。可见其高效性。另外,这个算法的编码复杂度很低,而且一般不会出错,所以应用范围也很广。
首先,我们定义M(a,b)函数是a与b的取最值函数(最大值或最小值),那么定义一个二维数组dpM[i][j],表示,从i开始,长度为2^j的一段元素中的最值,然后我们用二分的思想,把长度为2^j的一段拆分成等长度的两段,长度分别为2^(j-1),这样我们可以递推求解dpM[i][j],有dpM[i][j]=M(
dpM[i][j-1] , dpM[i+2^(j-1)][j-1])。如此一来,预处理工作就可以在O(nlogn)的时间下完成了。
查询时,我们取k为满足条件2^k <= R-L+1的最大整数。那么dpM[L][k]和dpM[R - 2^k + 1][k]这两个数所代表的区间可以完全覆盖所查询区间[L,R],最后的答案就是M(dpM[L][k]
, dpM[R - 2^k + 1][k])。在预处理之后,查询的时间复杂度是O(1)。
代码示例
在这份代码中,我将一维ST表的问题都集合到命名空间RMQ_st中,里面的成员有:
const int Maxn = 100005;//ST表的大小
int dpmax[Maxn][32];//最大值预处理数组
int dpmin[Maxn][32];//最小值预处理数组
int mm[Maxn];//log2(i)预处理数组
int val[Maxn];//原始数据
//原始数据从下标0开始编排 void prev_mm();//预处理log2(i)的过程
void prev_STmin(int n,int* array)//预处理最大值
void prev_STmax(int n,int* array)//预处理最小值
int query_min_with_array_index(int l,int r)//根据数组下标开始查询最小值
int query_max_with_array_index(int l,int r)//根据数组下标开始查询最大值
//自然排列法,也就是从1开始计数,不是从0开始计数
int query_min_with_natural_index(int l,int r)//根据自然排列法开始查询最小值
int query_max_with_natural_index(int l,int r)//根据自然排列法开始查询最大值
好了,代码奉上:
#include <iostream> #include <cstring> #include <cstdio> #include <cmath> #include <algorithm> using namespace std; #define DBG 0 #if DBG #include <cstdlib> #define pause system("pause") #define write(x) #x" = "<<(x)<<", " #define dout cout<<__LINE__<<" ||>> |" #else #define pause DBG #define write(x) #x" = "<<(x)<<", " #define dout DBG && cout<<__LINE__<<" ||>> |" #endif // DBG namespace RMQ_st{ const int Maxn = 100005; int dpmax[Maxn][32]; int dpmin[Maxn][32]; int mm[Maxn]; int val[Maxn]; void prev_mm(){ mm[1]=0; for (int i=2;i<Maxn;i++){ mm[i]=mm[i-1]; if ((1<<mm[i]+1) == i){ mm[i]++; } } return; } void prev_STmin(int n,int* array){ for (int i=n-1;i>=0;i--){ dpmin[i][0]=array[i]; for (int j=1;(i+(1<<j)-1)<n;j++){ dpmin[i][j]=min(dpmin[i][j-1],dpmin[i+(1<<j-1)][j-1]); } } } void prev_STmax(int n,int* array){ for (int i=n-1;i>=0;i--){ dpmax[i][0]=array[i]; for (int j=1;(i+(1<<j)-1)<n;j++){ dpmax[i][j]=max(dpmax[i][j-1],dpmax[i+(1<<j-1)][j-1]); } } } int query_min_with_array_index(int l,int r){ int len=r-l+1; int k=mm[len]; dout<<write(len)<<write(k)<<endl; pause; return min(dpmin[l][k],dpmin[r-(1<<k)+1][k]); } int query_max_with_array_index(int l,int r){ int len=r-l+1; int k=mm[len]; return max(dpmax[l][k],dpmax[r-(1<<k)+1][k]); } int query_min_with_natural_index(int l,int r){ return query_min_with_array_index(l-1,r-1); } int query_max_with_natural_index(int l,int r){ return query_max_with_array_index(l-1,r-1); } }; void solve(int t){ printf("Case %d:\n",t); int N,Q; scanf(" %d %d",&N,&Q); for (int i=0;i<N;i++){ scanf(" %d",&RMQ_st::val[i]); } RMQ_st::prev_STmin(N,RMQ_st::val); //RMQ_st::prev_STmax(N,RMQ_st::val); while (Q--){ int l,r; scanf(" %d %d",&l,&r); printf("%d\n",RMQ_st::query_min_with_natural_index(l,r)); //printf("%d\n",RMQ_st::query_max_with_natural_index(l,r)); } return; } int main(){ int T,tt=0; scanf(" %d",&T); RMQ_st::prev_mm(); while (T--){ solve(++tt); } return 0; }