题目描述：Balanced Lineup (POJ 3264)
题目要求在一个由N头牛组成的队列中，对于每个询问区间[L, R]，找出该区间内牛的高度差的最大值和最小值。
输入：
- 第一行包含两个整数N和Q，分别表示牛的数量和询问的数量。
- 接下来的N行，每行一个整数，表示每头牛的高度。
- 接下来的Q行，每行两个整数L和R，表示询问的区间。
输出：
- 对于每个询问，输出一个整数，表示区间[L, R]内牛的高度差的最大值和最小值之差。
解题思路：
-
暴力解法：
- 对于每个询问，直接遍历区间[L, R]，找出最大值和最小值，计算它们的差。
- 时间复杂度：O(Q * N)，对于大数据会超时。
-
优化解法：使用线段树（Segment Tree）：
- 线段树是一种高效处理区间查询和更新的数据结构。
- 构建两个线段树，一个用于查询区间的最大值，另一个用于查询区间的最小值。
具体步骤：
-
建树：
- 构建两个线段树，一个存储区间的最大值，另一个存储区间的最小值。
- 时间复杂度：O(N * log N)。
-
查询：
- 对于每个询问，分别在线段树中查询区间[L, R]的最大值和最小值。
- 时间复杂度：O(Q * log N)。
-
合并：
- 在线段树中，合并子区间的信息时，最大值的线段树取子区间的最大值，最小值的线段树取子区间的最小值。
代码实现（C++）：
#include
using namespace std;
const int MAXN = 50005;
struct SegmentTree {
int n;
vector
void build(const vector& arr) {
n = arr.size();
max_tree.resize(4 * n);
min_tree.resize(4 * n);
build_tree(1, 0, n - 1, arr);
}
void build_tree(int node, int start, int end, const vector& arr) {
if (start == end) {
max_tree[node] = arr[start];
min_tree[node] = arr[start];
} else {
int mid = (start + end) / 2;
build_tree(2 * node, start, mid, arr);
build_tree(2 * node + 1, mid + 1, end, arr);
max_tree[node] = max(max_tree[2 * node], max_tree[2 * node + 1]);
min_tree[node] = min(min_tree[2 * node], min_tree[2 * node + 1]);
}
}
int query_max(int l, int r) {
return query_max(1, 0, n - 1, l, r);
}
int query_max(int node, int start, int end, int l, int r) {
if (r < start || end < l) {
return INT_MIN;
}
if (l <= start && end <= r) {
return max_tree[node];
}
int mid = (start + end) / 2;
int p1 = query_max(2 * node, start, mid, l, r);
int p2 = query_max(2 * node + 1, mid + 1, end, l, r);
return max(p1, p2);
}
int query_min(int l, int r) {
return query_min(1, 0, n - 1, l, r);
}
int query_min(int node, int start, int end, int l, int r) {
if (r < start || end < l) {
return INT_MAX;
}
if (l <= start && end <= r) {
return min_tree[node];
}
int mid = (start + end) / 2;
int p1 = query_min(2 * node, start, mid, l, r);
int p2 = query_min(2 * node + 1, mid + 1, end, l, r);
return min(p1, p2);
} };
int main() {
int N, Q;
cin >> N >> Q;
vector
SegmentTree tree;
tree.build(heights);
for (int i = 0; i < Q; ++i) {
int L, R;
cin >> L >> R;
--L; --R; // Convert to 0-based index
int max_val = tree.query_max(L, R);
int min_val = tree.query_min(L, R);
cout << max_val - min_val << endl;
}
return 0;}
解释：
-
SegmentTree结构体：
- 包含两个数组
max_tree和min_tree，分别用于存储最大值和最小值的线段树。 build函数用于构建线段树。query_max和query_min函数用于查询区间的最大值和最小值。
- 包含两个数组
-
主函数：
- 读取输入数据。
- 构建线段树。
- 对于每个询问，查询区间的最大值和最小值，计算它们的差并输出。
通过使用线段树，我们可以将每个询问的时间复杂度降低到O(log N)，从而使得整体算法的时间复杂度为O(N log N + Q log N)，适用于大数据量的情况。
发表回复