NYOJ-119 士兵杀敌（三） ————–RMQ

士兵杀敌（三）

时间限制：2000ms | 内存限制：65535KB难度：5

描述

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

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

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

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

输入

只有一组测试数据

第一行是两个整数N,Q，其中N表示士兵的总数。Q表示南将军询问的次数。(1
随后的一行有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

1 /* 
  2    功能Function Description:     NYOJ-119
  3    开发环境Environment:          DEV C++ 4.9.9.1
  4    技术特点Technique:
  5    版本Version:
  6    作者Author:                   可笑痴狂
  7    日期Date:                      20120815
  8    备注Notes:                    ------RMQ算法(O(1)的时间复杂度查询区间最值)
  9 */
 10 /*
 11 //代码一：过程中都是存的最值的下标
 12 #include<stdio.h>
 13 #define MAX_N 100000+5
 14 #define MAX_L 17  //2^17>100000
 15 //定义存储的都是下标
 16 int num[MAX_N];
 17 int minN[MAX_N][MAX_L],maxN[MAX_N][MAX_L];
 18 //maxN[i][j]存储的是从编号i开始的连续2^j个数中最大值的下标
 19 //minN[i][j]存储的是从编号i开始的连续2^j个数中最小值的下标
 20 int max(int i,int j)
 21 {
 22     return num[i]>num[j]?i:j;
 23 }
 24 
 25 int min(int i,int j)
 26 {
 27     return num[i]<num[j]?i:j;
 28 }
 29 
 30 void preST(int n)
 31 {
 32     int i,j;
 33     for(i=0;i<n;++i)      //初始时候 num[minN[i][0]]=num[maxN[i][0]]=num[i]
 34         minN[i][0]=maxN[i][0]=i;
 35     for(i=1;(1<<i)<=n;++i)
 36         for(j=0;j+(1<<i)-1<n;++j)
 37         {
 38             maxN[j][i]=max(maxN[j][i-1],maxN[j+(1<<(i-1))][i-1]);
 39             minN[j][i]=min(minN[j][i-1],minN[j+(1<<(i-1))][i-1]);
 40         }
 41 }
 42 
 43 int ST(int a,int b,int flag)
 44 {
 45     int pow;
 46     --a;         因为是从0号单元开始存的，所以都减一
 47     --b;
 48     for(pow=1;(1<<pow)<b-a+1;++pow);
 49     --pow;
 50     if(flag)   //返回最大值
 51         return num[max(maxN[a][pow],maxN[b-(1<<pow)+1][pow])];//因为前后两段有重叠，所以注意是从后边向前计算边界
 52     else      //返回最小值
 53         return num[min(minN[a][pow],minN[b-(1<<pow)+1][pow])];
 54 }
 55 
 56 int main()
 57 {
 58     int i,n,m,a,b;
 59     while(scanf("%d%d",&n,&m)!=EOF)
 60     {
 61         for(i=0;i<n;++i)
 62             scanf("%d",&num[i]);
 63         preST(n);
 64         for(i=0;i<m;++i)
 65         {
 66             scanf("%d%d",&a,&b);
 67             if(a>b)
 68             {
 69                 a^=b;
 70                 b^=a;
 71                 a^=b;
 72             }
 73             printf("%d\n",ST(a,b,1)-ST(a,b,0));
 74         }
 75     }
 76     return 0;
 77 }
 78 
 79   */
 80 
 81 //代码二：也可以直接存最值
 82 #include<stdio.h>
 83 #define MAX_N 100000+5
 84 #define MAX_L 17  //2^17>100000
 85 
 86 int num[MAX_N];
 87 int minN[MAX_N][MAX_L],maxN[MAX_N][MAX_L];
 88 
 89 int max(int i,int j)
 90 {
 91     return i>j?i:j;
 92 }
 93 
 94 int min(int i,int j)
 95 {
 96     return i<j?i:j;
 97 }
 98 
 99 void preST(int n)
100 {
101     int i,j;        
102     for(i=1;(1<<i)<=n;++i)
103         for(j=0;j+(1<<i)-1<n;++j)
104         {
105             maxN[j][i]=max(maxN[j][i-1],maxN[j+(1<<(i-1))][i-1]);
106             minN[j][i]=min(minN[j][i-1],minN[j+(1<<(i-1))][i-1]);
107         }
108 }
109 
110 int ST(int a,int b,int flag)
111 {
112     int pow;
113     --a;
114     --b;
115     for(pow=1;(1<<pow)<b-a+1;++pow);
116     --pow;
117     if(flag)   //返回最大值
118         return max(maxN[a][pow],maxN[b-(1<<pow)+1][pow]);//因为前后两段有重叠，所以注意是从后边向前计算边界
119     else      //返回最小值
120         return min(minN[a][pow],minN[b-(1<<pow)+1][pow]);
121 }
122 
123 int main()
124 {
125     int i,n,m,a,b;
126     while(scanf("%d%d",&n,&m)!=EOF)
127     {
128         for(i=0;i<n;++i)
129         {
130             scanf("%d",&maxN[i][0]);
131             minN[i][0]=maxN[i][0];
132         }
133         preST(n);
134         for(i=0;i<m;++i)
135         {
136             scanf("%d%d",&a,&b);
137             if(a>b)
138             {
139                 a^=b;
140                 b^=a;
141                 a^=b;
142             }
143             printf("%d\n",ST(a,b,1)-ST(a,b,0));
144         }
145     }
146     return 0;
147 }

原文链接: https://www.cnblogs.com/dongsheng/archive/2012/08/15/2639930.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍