首页 > 代码库 > COGS182 [USACO Jan07] 均衡队形[RMQ]
COGS182 [USACO Jan07] 均衡队形[RMQ]
182. [USACO Jan07] 均衡队形
★★ 输入文件：lineup.in 输出文件：lineup.out 简单对比
时间限制：4 s 内存限制：128 MB
题目描述
农夫约翰的 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 行: 每行包含一个整数来表示区间上最大身高差。
样例输入
6 31734251 54 62 2
样例输出
630
刚感觉是没有修改的线段树，扫一眼左栏有人说st表，感觉自己智障了....
//// main.cpp// cogs182//// Created by Candy on 10/9/16.// Copyright © 2016 Candy. All rights reserved.//#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>using namespace std;typedef long long ll;const int N=1e5+5,MOD=1e9+7;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x;}int n,q,a[N],l,r;int mx[N][20],mn[N][20];void initRMQ(){ for(int i=1;i<=n;i++) mx[i][0]=mn[i][0]=a[i]; for(int j=1;j<=20;j++) for(int i=1;i+(1<<j)-1<=n;i++){ mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]); mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]); }}int qmx(int l,int r){ int k=log(r-l+1)/log(2); return max(mx[l][k],mx[r-(1<<k)+1][k]);}int qmn(int l,int r){ int k=log(r-l+1)/log(2); return min(mn[l][k],mn[r-(1<<k)+1][k]);}int main(int argc, const char * argv[]){ freopen("lineup.in","r",stdin); freopen("lineup.out","w",stdout); n=read();q=read(); for(int i=1;i<=n;i++) a[i]=read(); initRMQ(); for(int i=1;i<=q;i++){ l=read();r=read(); printf("%d\n",qmx(l,r)-qmn(l,r)); } return 0;}
COGS182 [USACO Jan07] 均衡队形[RMQ]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。