题目

1082 - Array Queries

PDF (English)

Statistics

Forum

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 ≤ 10⁵), q (1 ≤ q ≤ 50000). The next line contains
N space separated integers forming the array. There integers range in
[0, 10⁵].

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.

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;
}