题目描述
每天,农夫 John 的N(1 <= N <= 50,000)头牛总是按同一序列排队. 有一天, John 决定让一些牛们玩一场飞盘比赛. 他准备找一群在对列中为置连续的牛来进行比赛. 但是为了避免水平悬殊,牛的身高不应该相差太大. John 准备了Q (1 <= Q <= 180,000) 个可能的牛的选择和所有牛的身高 (1 <= 身高 <= 1,000,000). 他想知道每一组里面最高和最低的牛的身高差别.
输入格式
第1行：N,Q
第2到N+1行：每头牛的身高
第N+2到N+Q+1行：两个整数A和B，表示从A到B的所有牛。（1<=A<=B<=N）
输出格式
输出每行一个数，为最大数与最小数的差
输入样例
6 3
1
7
3
4
2
5
1 5
4 6
2 2
输出样例
6
3
0
Solution
这道题完全用ST表来解决就行了（反正也没有区间修改，况且我也懒得打线段树）。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
int n,m;
int d[180002];
int dp1[180002][55];
int dp2[180002][55];
int main() {
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++) {
scanf("%d",&d[i]);
}
for(int i=1; i<=n; i++) {
dp1[i][0]=d[i];
dp2[i][0]=d[i];
}
for(int j=1; (1<<j)<=n; j++) {
for(int i=1; i+(1<<j)-1<=n; i++) {
dp1[i][j]=max(dp1[i][j-1],dp1[i+(1<<j-1)][j-1]);
dp2[i][j]=min(dp2[i][j-1],dp2[i+(1<<j-1)][j-1]);
}
}
while(m--) {
int ll,rr;
scanf("%d%d",&ll,&rr);
int k=0;
while((1<<k+1)<=rr-ll+1)k++;
int maxi=max(dp1[ll][k],dp1[rr-(1<<k)+1][k]);
int mini=min(dp2[ll][k],dp2[rr-(1<<k)+1][k]);
printf("%d",maxi-mini);
printf("\n");
}
return 0;
}
|
