Balanced Lineup
Time Limit: 5000MS   Memory Limit: 65536K
Total Submissions: 64655   Accepted: 30135
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 ≤ ABN), 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.

Sample Input

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

Sample Output

6
3
0

Source

题意:就是求区间[l,r]的最大值与最小值之差
首先,介绍一下树状数组,树状数组的复杂度为O(logn),之所以这么快,它是用到了分块优化的思想
,比如:1-5就分为1、1-2、3、1-2-3-4、5;而树状数组最基本实现的就是求前缀和和区间单点更新;在本题中,我们也能效仿这样吗,当然。单点更新极值的话跟之前的一样;重点是求区间的极值,我们不能像求前缀和一样sum[r]-sum[l],那应该怎么办呢?
其实这里还是用到分块优化的思想,但是我们不能直接用Max[r],因为这里表示区间可能超出了我们要求的区间,但是我们可以利用一些包含在[l,r]这里面的块,从而降低复杂度。
假设我们暴力的话,就是从右往左遍历一遍a数组然后取最值,那么在这之中,如果有一些分块在[l,r]之中,就可以直接使用这些块了,就不用去遍历他们,但是遇到有的块超出了[l,r],我们就只能直接比较a[r]了。
代码:
#include<iostream>
#include<string.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define mod 1000000007
#define INF 0x3f3f3f3f
#define MAX 50005
int Max[MAX],Min[MAX];
int a[MAX];
int n,q;
inline void read(int &x){
char ch;
bool flag=false;
for (ch=getchar();!isdigit(ch);ch=getchar())if (ch=='-') flag=true;
for (x=;isdigit(ch);x=x*+ch-'',ch=getchar());
x=flag?-x:x;
}
inline void write(int x){
static const int maxlen=;
static char s[maxlen];
if (x<) { putchar('-'); x=-x;}
if(!x){ putchar(''); return; }
int len=; for(;x;x/=) s[len++]=x % +'';
for(int i=len-;i>=;--i) putchar(s[i]);
}
int lowbit(int x)
{
return x&-x;
}
void updata(int i,int val)
{
while(i<=n)
{
Min[i]=min(Min[i],val);
Max[i]=max(Max[i],val);
i+=lowbit(i);
}
}
int query(int l,int r)
{
int maxn=a[l],minn=a[r];
while()
{
maxn=max(maxn,a[r]),minn=min(minn,a[r]);
if(l==r) break;
for(r-=;r-l>=lowbit(r);r-=lowbit(r))
maxn=max(Max[r],maxn),minn=min(minn,Min[r]);
}
return maxn-minn;
}
int main()
{
memset(Min,INF,sizeof(Min));
read(n);read(q);
for(int i=;i<=n;i++){
read(a[i]);
updata(i,a[i]);
}
while(q--)
{
int a,b;
read(a),read(b);
write(query(a,b));
putchar('\n');
}
return ;
}

时间复杂度近似为log2(n)。

参考博客:https://www.cnblogs.com/mypride/p/5002556.html

https://blog.csdn.net/u012602144/article/details/52734329

 

最新文章

  1. cat hesA/Models/score_tgt.sc| awk &#39;{ print $2,$19}&#39; | sort -n -k 1
  2. (二)STM32中中断优先级理解
  3. git提交代码步骤
  4. C51 的编程规范
  5. keil对51单片机变量和函数的编译处理
  6. Insertion Sort List —— LeetCode
  7. Java实现八皇后
  8. jdbc接口api
  9. vmware9安装centos和Mac经验总结
  10. 4种Java引用浅解
  11. 2014年度辛星完全解读html部分
  12. 纯JS写动态分页样式效果
  13. Jmeter之接口测试
  14. 微软Skype Linux客户端全新发布
  15. FastDFS 分布式文件系统的安装与使用(单节点)
  16. Randomized Online PCA Algorithms with Regret Bounds that are Logarithmic in the Dimension
  17. fastjson与各类型的转换
  18. BZOJ 1800 [Ahoi2009]fly 飞行棋
  19. nodejs的express框架
  20. java学习笔记1--基础知识

热门文章

  1. 安装weblogic界面安装
  2. 20191107PHP创建数组练习
  3. 20180105-Python中dict的使用方法
  4. android5.1修改系统默认音量
  5. win10 中文
  6. 【LeetCode】字符串 string(共112题)
  7. 消费者与生产者---LinkedList方式模拟
  8. JDBC简单总结
  9. 自建云存储:Nextcloud vs. ownCloud vs. Seafile
  10. 【BZOJ3756】Pty的字符串(广义后缀自动机)