我是靠谱客的博主 忧心烤鸡,这篇文章主要介绍【cogs182】【USACO Jan07】均衡队形【st表】,现在分享给大家,希望可以做个参考。

题目描述

农夫约翰的 N (1 ≤ N ≤ 50,000) 头奶牛,每天挤奶时总会按同样的顺序站好。一日,农夫约翰决定为奶牛们举行一个“终极飞盘”比赛。为简化问题,他将从奶牛队列中选出一个连续区间来进行游戏。不过,参加游戏的奶牛要玩的开心的话就不能在身高上差距太大。

农夫约翰制定了 Q (1 ≤ Q ≤ 200,000) 个预定的参赛组,给出它们的身高 (1 ≤ 身高 ≤ 1,000,000)。对每个参赛组,他需要你帮助确定组中最高牛和最低牛的身高差。

输入格式

  • 第 1 行: 两个空格隔开的整数,N 和 Q。
  • 第 2..N+1 行: 第 i+1 行包含一个整数表示第 i 头牛的身高。
  • 第 N+2..N+Q+1 行: 两个整数 A 和 B(1 ≤ A ≤ B ≤ N),表示一个从 A 到 B 的参赛组区间。

输出格式

  • 第 1..Q 行: 每行包含一个整数来表示区间上最大身高差。

样例输入

复制代码
1
2
3
4
5
6
7
8
9
10
6 3 1 7 3 4 2 5 1 5 4 6 2 2

样例输出

复制代码
1
2
3
6 3 0
复制代码
1
题解:st表练习题。。
复制代码
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
复制代码
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,a,b,q,ffmin[60000][30],ffmax[60000][30];
int in()
{
    int x=0;
    char ch;
    ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x;
}
int main()
{
	freopen("lineup.in","r",stdin);
	freopen("lineup.out","w",stdout);
	scanf("%d%d",&n,&q);
	for (int i=1;i<=n;i++)
	  {
		a=in();
		ffmin[i][0]=a;ffmax[i][0]=a;
	  }
	for (int j=1;j<=20;j++)
	  for (int i=1;i<=n;i++)
	    if (i+(1<<j)-1<=n)
		  {
			 ffmin[i][j]=min(ffmin[i][j-1],ffmin[i+(1<<(j-1))][j-1]);
			 ffmax[i][j]=max(ffmax[i][j-1],ffmax[i+(1<<(j-1))][j-1]);
		  } 
		 else break;
	 for (int i=1;i<=q;i++)
	   {
		   int k,maxx,minn;
		   a=in();b=in();
		   k=(int)(log(b-a+1.0)/log(2.0));
		   maxx=max(ffmax[a][k],ffmax[b-(1<<k)+1][k]);
		   minn=min(ffmin[a][k],ffmin[b-(1<<k)+1][k]);
		   printf("%dn",maxx-minn);
	   }
}


最后

以上就是忧心烤鸡最近收集整理的关于【cogs182】【USACO Jan07】均衡队形【st表】的全部内容,更多相关【cogs182】【USACO内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(74)

评论列表共有 0 条评论

立即
投稿
返回
顶部