poj 3264(RMQ或者线段树)
2024-09-01 12:01:55
Balanced Lineup
Time Limit: 5000MS | Memory Limit: 65536K | |
Total Submissions: 42929 | Accepted: 20184 | |
Case Time Limit: 2000MS |
Description
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.
Input
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 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.
Output
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.
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.
Sample Input
6 3
1
7
3
4
2
5
1 5
4 6
2 2
Sample Output
6
3
0
Source
题意:区间最大值与最小值之差RMQ版:(不懂的可以参考blog)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
#define N 50010 int a[N];
int max_dp[N][];
int min_dp[N][];
int MAX(int i,int j){
if(i>=j) return i;
return j;
}
int MIN(int i,int j){
if(i<=j) return i;
return j;
}
void init_MAX_RMQ(int n){
for(int i=;i<=n;i++) max_dp[i][]=a[i];
for(int j=;(<<j)<=n;j++){
for(int i=;i<=n-(<<j)+;i++){
///F[i, j]=max(F[i,j-1], F[i + 2^(j-1),j-1])。
max_dp[i][j] = MAX(max_dp[i][j-],max_dp[i+(<<(j-))][j-]);
}
}
}
int MAX_RMQ(int a,int b){
int k = (int)(log(b-a+1.0)/log(2.0));
///RMQ(A, i, j)=min{F[i,k],F[j-2^k+1,k]}
return MAX(max_dp[a][k],max_dp[b-(<<k)+][k]);
}
void init_MIN_RMQ(int n){
for(int i=;i<=n;i++) min_dp[i][]=a[i];
for(int j=;(<<j)<=n;j++){
for(int i=;i<=n-(<<j)+;i++){
min_dp[i][j] = MIN(min_dp[i][j-],min_dp[i+(<<(j-))][j-]);
}
}
}
int MIN_RMQ(int a,int b){
int k = (int)(log(b-a+1.0)/log(2.0));
return MIN(min_dp[a][k],min_dp[b-(<<k)+][k]);
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF){
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
}
init_MAX_RMQ(n);
init_MIN_RMQ(n);
while(m--){
int a,b;
scanf("%d%d",&a,&b);
printf("%d\n",MAX_RMQ(a,b)-MIN_RMQ(a,b));
}
}
return ;
}
线段树:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
#define N 50010 struct Tree{
int l,r;
int Max,Min;
}tree[*N];
int a[N];
int MAX_VALUE;
int MIN_VALUE;
int MAX(int i,int j){
if(i>=j) return i;
return j;
}
int MIN(int i,int j){
if(i<=j) return i;
return j;
}
void PushUp(int idx){
tree[idx].Max = MAX(tree[idx<<].Max,tree[idx<<|].Max);
tree[idx].Min = MIN(tree[idx<<].Min,tree[idx<<|].Min);
}
void build(int l,int r,int idx){
tree[idx].l = l;
tree[idx].r = r;
if(l==r) {
tree[idx].Max = tree[idx].Min = a[l];
return ;
}
int mid=(l+r)>>;
build(l,mid,idx<<);
build(mid+,r,idx<<|);
PushUp(idx);
}
void query(int l,int r,int idx){
if(tree[idx].l==l&&tree[idx].r==r){
MAX_VALUE = MAX(MAX_VALUE,tree[idx].Max);
MIN_VALUE = MIN(MIN_VALUE,tree[idx].Min);
return;
}
int mid=(tree[idx].l+tree[idx].r)>>;
if(mid>=r) query(l,r,idx<<);
else if(mid<l) query(l,r,idx<<|);
else{
query(l,mid,idx<<);
query(mid+,r,idx<<|);
}
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF){
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
}
build(,n,);
while(m--){
int b,c;
scanf("%d%d",&b,&c);
MAX_VALUE=-;
MIN_VALUE=;
query(b,c,);
printf("%d\n",MAX_VALUE-MIN_VALUE);
}
}
return ;
}
最新文章
- 未能加载文件或程序集“System.Data.SQLite”或它的一个依赖。试图加载格式不正确的程序
- DDDD
- Angular ng-repeat
- pat_1009
- 追踪CM_CONTROLCHANGE消息的产生和执行过程,可以较好的领会VCL的思想(就是到处通知,但耦合性很弱)
- LVM(1)
- c# 小数的处理
- openStack deep dive,Retake Policy
- WPF与Win32互操作
- CentOS7下安装MySQL的安装与配置(yum) (转)
- POJ1331 Multiply(strtol函数练习)
- Java启动工程时,加载固定数据到Map中(不用每次访问数据库)
- 格雷码(Gray code)仿真
- c++11 输出时间
- openCV函数
- .net core 开发接口前端调用时提示错误 405
- Drupal8学习之路--官网文档碎碎记--主题篇
- asp.net core microservices 架构之 分布式自动计算(一)
- python基础 列表和字符串
- gcm 被微信弃用的原因