牛的身高不应该相差太大. John 准备了Q (1 &lt,牛的身高不应有相差太大. 约翰 准备了Q (1 &lt

难题背景

题目叙述:

每一日,农夫 John 的N(1 <= N <= 50,000)头牛总是按同一序列排队.
有一天, John 决定让部分牛们玩一场飞盘比赛.
他准备找一群在对列中为置延续的牛来拓展比赛.
可是为了防止水平悬殊,牛的身高不应有相差太大. John 准备了Q (1 <= Q
<= 180,000) 个只怕的牛的选用和颇具牛的身高 (1 <= 身高 <=
1,000,000). 他想驾驭每一组里面最高和最低的牛的身高差别.

输入:

第1行:N,Q

第三到N+1行:每头牛的身高

第N+2到N+Q+1行:三个整数A和B,表示从A到B的全体牛。(1<=A<=B<=N)

输出:

输出每行3个数,为最大数与小小数的差

题材背景

难点叙述:

每一日,农夫 John 的N(1 <= N <= 50,000)头牛总是按同一体系排队.
有一天, John 决定让有个别牛们玩一场飞盘比赛.
他准备找一群在对列中为置一而再的牛来进展比赛.
然而为了幸免水平悬殊,牛的身高不该相差太大. John 准备了Q (1 <= Q
<= 180,000) 个可能的牛的抉择和享有牛的身高 (1 <= 身高 <=
1,000,000). 他想清楚每一组里面最高和最低的牛的身高差距.

输入:

第1行:N,Q

第壹到N+1行:每头牛的身高

第N+2到N+Q+1行:多个整数A和B,表示从A到B的享有牛。(1<=A<=B<=N)

输出:

输出每行2个数,为最大数与纤维数的差

标题叙述

For the daily milking, Farmer John’s N cows (1 ≤ N ≤ 50,000) always line
up in the same order. One day Farmer John decides to organize a game of
Ultimate Frisbee with some of the cows. To keep things simple, he will
take a contiguous range of cows from the milking lineup to play the
game. However, for all the cows to have fun they should not differ too
much in height.

Farmer John has made a list of Q (1 ≤ Q ≤ 200,000) potential groups of
cows and their heights (1 ≤ height ≤ 1,000,000). For each group, he
wants your help to determine the difference in height between the
shortest and the tallest cow in the group.

3个农夫有N头牛,每头牛的惊人不等,大家要求找出最高的牛和最低的牛的冲天差。

题材叙述

For the daily milking, Farmer John’s N cows (1 ≤ N ≤ 50,000) always line
up in the same order. One day Farmer John decides to organize a game of
Ultimate Frisbee with some of the cows. To keep things simple, he will
take a contiguous range of cows from the milking lineup to play the
game. However, for all the cows to have fun they should not differ too
much in height.

Farmer John has made a list of Q (1 ≤ Q ≤ 200,000) potential groups of
cows and their heights (1 ≤ height ≤ 1,000,000). For each group, he
wants your help to determine the difference in height between the
shortest and the tallest cow in the group.

壹个庄稼汉有N头牛,每头牛的可观不等,我们要求找出最高的牛和压低的牛的万丈差。

输入输出样例

输入样例#1: 复制

6 3
1
7
3
4
2
5
1 5
4 6
2 2

输出样例#1: 复制

6
3
0

裸地ST表

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 #define LL long long 
 7 #define lb(x)    ((x)&(-x))
 8 using namespace std;
 9 const int MAXN=500001;
10 inline int read()
11 {
12     char c=getchar();int x=0,f=1;
13     while(c<'0'||c>'9')    {if(c=='-')    f=-1;c=getchar();}
14     while(c>='0'&&c<='9')    x=x*10+c-48,c=getchar();return x*f;
15 }
16 int dpmin[MAXN][21];
17 int dpmax[MAXN][21];
18 int n,m;
19 int getmax(int l,int r)
20 {
21     int k=log2(r-l+1);
22     return max(dpmax[l][k],dpmax[r-(1<<k)+1][k]);
23 }
24 int getmin(int l,int r)
25 {
26     int k=log2(r-l+1);
27     return min(dpmin[l][k],dpmin[r-(1<<k)+1][k]);
28 }
29 int main()
30 {
31     n=read();m=read();
32     for(int i=1;i<=n;i++)
33         dpmax[i][0]=read(),dpmin[i][0]=dpmax[i][0];
34     for(int i=1;i<=19;i++)
35         for(int j=1;j<=n&&j+(1<<i)-1<=n;j++)
36             dpmax[j][i]=max(dpmax[j][i-1],dpmax[j+(1<<i-1)][i-1]),
37             dpmin[j][i]=min(dpmin[j][i-1],dpmin[j+(1<<i-1)][i-1]);
38     for(int i=1;i<=m;i++)
39     {
40         int x=read(),y=read();
41         printf("%d\n",getmax(x,y)-getmin(x,y));
42     }
43     return 0;
44 }

 

输入输出格式

输入格式:

 

Line 1: Two space-separated integers, N and Q.

Lines 2..N+1: Line i+1 contains a single integer that is the height of
cow i

Lines N+2..N+Q+1: Two integers A and B (1 ≤ A ≤ B ≤ N), representing the
range of cows from A to B inclusive.

 

输出格式:

 

Lines 1..Q: Each line contains a single integer that is a response to a
reply and indicates the difference in height between the tallest and
shortest cow in the range.

 

输入输出格式

输入格式:

 

Line 1: Two space-separated integers, N and Q.

Lines 2..N+1: Line i+1 contains a single integer that is the height of
cow i

Lines N+2..N+Q+1: Two integers A and B (1 ≤ A ≤ B ≤ N), representing the
range of cows from A to B inclusive.

 

出口格式:

 

Lines 1..Q: Each line contains a single integer that is a response to a
reply and indicates the difference in height between the tallest and
shortest cow in the range.

 

输入输出样例

输入样例#1: 复制

6 3
1
7
3
4
2
5
1 5
4 6
2 2

出口样例#1: 复制

6
3
0

裸地ST表

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 #define LL long long 
 7 #define lb(x)    ((x)&(-x))
 8 using namespace std;
 9 const int MAXN=500001;
10 inline int read()
11 {
12     char c=getchar();int x=0,f=1;
13     while(c<'0'||c>'9')    {if(c=='-')    f=-1;c=getchar();}
14     while(c>='0'&&c<='9')    x=x*10+c-48,c=getchar();return x*f;
15 }
16 int dpmin[MAXN][21];
17 int dpmax[MAXN][21];
18 int n,m;
19 int getmax(int l,int r)
20 {
21     int k=log2(r-l+1);
22     return max(dpmax[l][k],dpmax[r-(1<<k)+1][k]);
23 }
24 int getmin(int l,int r)
25 {
26     int k=log2(r-l+1);
27     return min(dpmin[l][k],dpmin[r-(1<<k)+1][k]);
28 }
29 int main()
30 {
31     n=read();m=read();
32     for(int i=1;i<=n;i++)
33         dpmax[i][0]=read(),dpmin[i][0]=dpmax[i][0];
34     for(int i=1;i<=19;i++)
35         for(int j=1;j<=n&&j+(1<<i)-1<=n;j++)
36             dpmax[j][i]=max(dpmax[j][i-1],dpmax[j+(1<<i-1)][i-1]),
37             dpmin[j][i]=min(dpmin[j][i-1],dpmin[j+(1<<i-1)][i-1]);
38     for(int i=1;i<=m;i++)
39     {
40         int x=read(),y=read();
41         printf("%d\n",getmax(x,y)-getmin(x,y));
42     }
43     return 0;
44 }

 

相关文章