RMQ算法 NYOJ-119 士兵杀敌(三)

描述

南将军统率着N个士兵,士兵分别编号为1~N,南将军经常爱拿某一段编号内杀敌数最高的人与杀敌数最低的人进行比较,计算出两个人的杀敌数差值,用这种方法一方面能鼓舞杀敌数高的人,另一方面也算是批评杀敌数低的人,起到了很好的效果。

所以,南将军经常问军师小工第i号士兵到第j号士兵中,杀敌数最高的人与杀敌数最低的人之间军功差值是多少。

现在,请你写一个程序,帮小工回答南将军每次的询问吧。

注意,南将军可能询问很多次。

输入

只有一组测试数据

第一行是两个整数N,Q,其中N表示士兵的总数。Q表示南将军询问的次数。(1<N<=100000,1<Q<=1000000)

随后的一行有N个整数Vi(0<=Vi<100000000),分别表示每个人的杀敌数。

再之后的Q行,每行有两个正正数m,n,表示南将军询问的是第m号士兵到第n号士兵。

输出

对于每次询问,输出第m号士兵到第n号士兵之间所有士兵杀敌数的最大值与最小值的差。

样例输入

5 2

1 2 6 9 3

1 2

2 4

样例输出

1

7

概述

RMQ(Range Minimum/Maximum Query),即区间最值查询,是指这样一个问题:对于长度为n的数列A,回答若干询问RMQ(A,i,j)(i,j<=n),返回数列A中下标在i,j之间的最小/大值。这两个问题是在实际应用中经常遇到的问题,当然,该问题也可以用线段树(也叫区间树)解决,算法复杂度为:O(N)~O(logN)

如果只有一次询问,那样只有一遍for就可以搞定,但是如果有许多次询问就无法在很快的时间处理出来。

这是一种在线算法。所谓在线算法,是指用户每输入一个查询便马上处理一个查询。该算法一般用较长的时间做预处理,待信息充足以后便可以用较少的时间回答每个查询。

O(nlogn)时间内进行预处理,然后在O(1)时间内回答每个查询。

首先是预处理,用动态规划(DP)解决。

设A[i]是要求区间最值的数列,F[i, j]表示从第i个数起连续2^j个数中的最大值。(DP的状态)

例如:

A数列为:3 2 4 5 6 8 1 2 9 7

F[1,0]表示第1个数起,长度为2^0=1的最大值,其实就是3这个数。同理 F[1,1] = max(3,2) = 3, F[1,2]=max(3,2,4,5) = 5,F[1,3] = max(3,2,4,5,6,8,1,2) = 8;

并且我们可以容易的看出F[i,0]就等于A[i]。(DP的初始值)

这样,DP的状态、初值都已经有了,剩下的就是状态转移方程。

我们把F[i,j]平均分成两段(因为f[i,j]一定是偶数个数字),从 i 到i + 2 ^ (j - 1) - 1为一段,i + 2 ^ (j - 1)到i + 2 ^ j - 1为一段(长度都为2 ^ (j - 1))。用上例说明,当i=1,j=3时就是3,2,4,5 和 6,8,1,2这两段。F[i,j]就是这两段各自最大值中的最大值。于是我们得到了状态转移方程F[i, j]=max(F[i,j-1], F[i + 2^(j-1),j-1])。

查询

假设我们需要查询区间[l, r]中的最小值,令k = log2(r - l + 1); 则区间[l, r]的最小值RMQ[l,r] = min(mn[l][k], mn[r - (1 << k) + 1][k]);

那么为什么这样就可以保证为区间最值?

mn[l][k]维护的是[l, l + 2 ^ k - 1], mn[r - (1 << k) + 1][k]维护的是[r - 2 ^ k + 1, r] 。

区间前后维护!

那么我们只要保证r - 2 ^ k + 1 <= l + 2 ^ k - 1就能保证RMQ[l,r] = min(mn[l][k], mn[r - (1 << k) + 1][k]);

我们用分析法来证明下:

若r - 2 ^ k + 1 <= l + 2 ^ k - 1;

则r - l + 2 <= 2 ^ (k + 1);

又因为 k = log2(r - l + 1);

则r - l + 2 <= 2 *(r - l + 1);

则r - l >= 0;

显然可得。
我们来举个例子 l = 4, r = 6;

此时k = log2(r - l + 1) = log2(3) = 1;

所以RMQ[4, 6] = min(mn[4][1], mn[5][1]);

mn[4][1] = 4, mn[5][1] = 2;

所以RMQ[4, 6] = min(mn[4][1], mn[5][1]) = 2;

我们很容易看出来了答案是正确的。

dp,我的dp,我要拿到大国一!

NYOJ-119 士兵杀敌(三)【RMQ算法】

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;

const int N = 100010;
int maxsum[N][20], minsum[N][20];

void RMQ(int num) //预处理->O(nlogn)
{
        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]);
    }
}

int main()
{
        int num, query;
        int src, des;
        scanf("%d %d", &num, &query);
            for(int i = 1; i <= num; ++i) //输入信息处理
            {
                  scanf("%d", &maxsum[i][0]);
                  minsum[i][0] = maxsum[i][0];
            }
               RMQ(num);
             while(query--) //O(1)查询
             {
                      scanf("%d %d", &src, &des);
                      int k = (int)(log(des - src + 1.0) / log(2.0));
                      int maxres = max(maxsum[src][k], maxsum[des - (1 << k) + 1][k]);
                      int minres = min(minsum[src][k], minsum[des - (1 << k) + 1][k]);
                      printf("%d\n", maxres - minres);
               }
         return 0;
}

原文发布于微信公众号 - ACM算法日常(acm-clan)

原文发表时间:2018-11-10

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

BZOJ1061: [Noi2008]志愿者招募(线性规划)

  申奥成功后,布布经过不懈努力,终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难

16940
来自专栏数据科学

股票实时流计算

var element = $('#61901593-c697-4e0e-ad17-c8f2c3fae6ae'); {"model_id": "8629...

19440
来自专栏小樱的经验随笔

江西理工大学南昌校区cool code竞赛

      这次比赛原本就是来打酱油的,想做个签到题就走!一开始不知道1002是签到题,一直死磕1001,WA了四发过了,回头一看Rank,三十名,我靠!看了1...

464110
来自专栏owent

ECUST 09年 校赛个人赛第三场部分解题报告(A,D,F,I)

首先是VC6.0的algorithm里没有min函数,而我用min做变量名导致CE4次,找了半天才找出来

10510
来自专栏算法修养

HDU 1243 反恐训练营(最长公共序列)

反恐训练营 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Jav...

28370
来自专栏沈唁志

PHP根据身份证号码验证、获取星座、生肖和性别函数

49520
来自专栏CreateAMind

carla无人驾驶模拟中文项目 carla_simulator_Chinese

https://github.com/xfqbuaa/carla_simulator_Chinese

14630
来自专栏女程序员的日常

面试——经典问题1

1、阶梯问题 问题描述:一个阶梯有n个级,一个人要走完这个阶梯,一步可以走一级或两级,问:共有多少个方案? 解决思路:当n=1时候,只有一种走法,当n=2时候有...

22610
来自专栏ACM算法日常

PAT-CCCC练习:L2-020.功夫传人(并查集)

题目:https://www.patest.cn/contests/gplt/L2-020

13720
来自专栏数据结构与算法

P1007 独木桥

题目背景 战争已经进入到紧要时间。你是运输小队长,正在率领运输部队向前线运送物资。运输任务像做题一样的无聊。你希望找些刺激,于是命令你的士兵们到前方的一座独木桥...

27980

扫码关注云+社区

领取腾讯云代金券