首页 > 代码库 > NYIST 119 士兵杀敌（三）
NYIST 119 士兵杀敌（三）
士兵杀敌（三）
时间限制：2000 ms | 内存限制：65535 KB
难度：5
描述
南将军统率着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
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib>10 #include <string>11 #include <set>12 #include <stack>13 #define LL long long14 #define pii pair<int,int>15 #define INF 0x3f3f3f3f16 using namespace std;17 const int maxn = 100010;18 int maxv[maxn][32],minv[maxn][32];19 int main() {20 int n,m,x,y;21 while(~scanf("%d %d",&n,&m)){22 for(int i = 0; i < n; ++i){23 scanf("%d",&maxv[i][0]);24 minv[i][0] = maxv[i][0];25 }26 for(int i = n - 1; i >= 0; --i){27 for(int j = 1; i + (1<<j) <= n; j++){28 minv[i][j] = min(minv[i][j-1],minv[i+(1<<(j-1))][j-1]);29 maxv[i][j] = max(maxv[i][j-1],maxv[i+(1<<(j-1))][j-1]);30 }31 }32 while(m--){33 scanf("%d %d",&x,&y);34 int r = log2(y - x + 1);35 int theMax = max(maxv[x-1][r],maxv[y-(1<<r)][r]);36 int theMin = min(minv[x-1][r],minv[y-(1<<r)][r]);37 printf("%d\n",theMax - theMin);38 }39 }40 return 0;41 }
NYIST 119 士兵杀敌（三）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。