精华内容
参与话题
问答
  • RMQ

    2013-09-11 16:16:30
    RMQ 描述 测试说明与提交 提交状态 题目设置 题目描述: 给 N 个数字 a[1], a[2], ..., a[N] 给 2 个角标 i, j,求 a[i..j] 的最大值 注意,角标从 1 开始 输入格式: 有 1 组测试数据。第一行为数字个数 N,第...

    RMQ

    题目描述:

    给 N 个数字 a[1], a[2], ..., a[N]
    给 2 个角标 i, j,求 a[i..j] 的最大值
    注意,角标从 1 开始

    输入格式:

    有 1 组测试数据。第一行为数字个数 N,第二行有 N 个数字,用空格隔开
    第三行起有多组询问,每组询问占一行,包含两个数字 i, j
    共有 6 轮测试。

    输出格式:

    对每个询问输出一行,包括一个数字,为最大值

    数据范围:

    每个数字保证在 int 范围内
    数字个数在 1 到 5,000 之间
    询问个数在 1 到 10,000 之间

    样例输入:

    5
    2 4 5 3 2
    1 5
    4 5

    样例输出:

    5
    3


    展开全文
  • rmq

    2016-07-20 16:17:38
    rmq主要用于区间最值查询,算法复杂度O(nlogn)。 运用rmq算法,我们可以先预处理出所有的区间最值,即:有n个数字,当我们需要多次查询(l,r)(1=<l,r<=n)区间内的最值时 ,我们就可以用rmq...

    rmq主要用于区间最值查询,算法复杂度O(nlogn)。

    运用rmq算法,我们可以先预处理出所有的区间最值,即:有n个数字,当我们需要多次查询(l,r)(1=<l,r<=n)区间内的最值时 ,我们就可以用rmq解决。

     

    核心代码:

     

    void RMQ(int num) //预处理  
    {  
        for(int j = 1; j < 20; ++j)  
            for(int i = 1; i <= num; ++i)  
                if(i + (1 << j) - 1 <= num)  
                {  
                    maxsum[i][j] = max(maxsum[i][j - 1], maxsum[i + (1 << (j - 1))][j - 1]);  
                    minsum[i][j] = min(minsum[i][j - 1], minsum[i + (1 << (j - 1))][j - 1]);  
                }  
    }  


    这一部分就是我们的预处理,主要是用dp解决的,这里有点类似区间dp吧。

     

    假使我们现在有数组a :

    1 2 4 6 5 2 1 

    数组f[i,j]代表,我们区间的(i,i+j^2-1) 区间的最值, 即我们以i位置开头,长度为j^2的区间的最值。

     

    for(int j = 1; j < 20; ++j) 

    这里我们的第一层for,枚举的是层数,也可以说是区间的长度, 因为我们递推时 用两个len1 推出一个len2,用两个len2 推出一个len4 以此类推 。

     

     

    for(int i = 1; i <= num; ++i)

    第二层for我们枚举的是区间的起点位置。

     

    这样  当我们求区间(1,4)时,就相当于求 max or min((1,2),(3,4))。

     

    然后对于区间(1,3),我们是怎么处理的呢,= max or min((1,2),(2,3)),在这里我们需要寻找最小的可以覆盖目标区间的2^x*2。

     

    这样我们就可以利用原来我们dp的预处理来解决我们的问题,这也算是rmq一个优化的地方吧。

    查询:(i,j) -》因为这里区间的长度为j-i+1,所以我们可以取k=log2(j-i+1),有 (i,j)=max or min ((f(i,k)),(j-2^k+1,k))。

     

     

    展开全文

空空如也

1 2 3 4 5 ... 20
收藏数 8,176
精华内容 3,270
关键字:

rmq