POJ3264(线段树求区间最大最小值)
2024-08-28 12:48:20
Balanced Lineup
Time Limit: 5000MS | Memory Limit: 65536K | |
Total Submissions: 41162 | Accepted: 19327 | |
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.
Sample Input
6 3
1
7
3
4
2
5
1 5
4 6
2 2
Sample Output
6
3
0
Source
晚上BC、CF,敲一发线段树练练手感
/*
* @Author: LinK
* @Date: 2015-10-31 18:20:11
* @Last Modified by: LinK
* @Last Modified time: 2015-10-31 18:27:30
*/ #include <map>
#include <set>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <cstdio>
#include <string>
#include <utility>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define eps 1e-8
#define randin srand((unsigned int)time(NULL))
#define input freopen("input.txt","r",stdin)
#define debug(s) cout << "s = " << s << endl;
#define outstars cout << "*************" << endl;
const double PI = acos(-1.0);
const int inf = 0x3f3f3f3f;
const int INF = 0x7fffffff;
typedef long long ll; const int maxn = ; struct Node {
int ma, mi;
} tree[maxn << ]; int num[maxn];
int n, q; void build(int rt, int l, int r) {
if (l == r) {
tree[rt].ma = num[l];
tree[rt].mi = num[l];
return;
}
int mid = (l + r) >> ;
build(rt << , l, mid);
build(rt << | , mid + , r);
tree[rt].ma = max(tree[rt << ].ma, tree[rt << | ].ma);
tree[rt].mi = min(tree[rt << ].mi, tree[rt << | ].mi);
} int query_ma(int rt, int l, int r, int L, int R) {
if (L <= l && R >= r) return tree[rt].ma;
int mid = (l + r) >> ;
if (R <= mid) return query_ma(rt << , l, mid, L, R);
if (L > mid) return query_ma(rt << | , mid + , r, L, R);
return max(query_ma(rt << , l, mid, L, R), query_ma(rt << | , mid + , r, L, R));
} int query_mi(int rt, int l, int r, int L, int R) {
if (L <= l && R >= r) return tree[rt].mi;
int mid = (l + r) >> ;
if (R <= mid) return query_mi(rt << , l, mid, L, R);
if (L > mid) return query_mi(rt << | , mid + , r, L, R);
return min(query_mi(rt << , l, mid, L, R), query_mi(rt << | , mid + , r, L, R));
} int main() {
while (~scanf("%d %d", &n, &q)) {
for (int i = ; i <= n; i ++) scanf("%d", &num[i]);
build(, , n);
int a, b;
while (q --) {
scanf("%d %d", &a, &b);
int ma = query_ma(, , n, a, b);
int mi = query_mi(, , n, a, b);
printf("%d\n", ma - mi);
}
} return ;
}
最新文章
- 外媒速递:十大最佳心理学概念助你提升Web设计效果
- 20160620001 FileUpload控件获取上传文件的路径
- Quartz2D学习笔记
- Android列表视图(List View)
- 讲讲金融业务(一)--自助结算终端POS
- 关于volatile的可见性和禁止指令重排序的疑惑
- 四五月份:关键词是沟通、绘画和SQL
- 【dp】P1434 [SHOI2002]滑雪
- [转] 如何轻松愉快地理解条件随机场(CRF)?
- [转]python3之日期和时间
- Java NIO- 最好文档
- NALU数据打RTP包流程详解
- 在Linux上git pull线上仓库代码时,出现error: Your local changes to the following files would be overwritten by merge
- Linux 中指定启动 tomcat 的 jdk 版本
- Dictionary 的几种遍历方法
- Spanner:谷歌新一代全球部署的列式数据库
- JVM学习(一)
- java 框架收藏
- 网站访问日志User Agent对照表
- [转]json+JSONObject+JSONArray 结合使用