POJ 3264 Balanced Lineup——线段树

POJ 3264 Balanced Lineup——线段树

题意：求一个区间的最大值减最小值

思路：建立两棵线段树维护最大值和最小值，设置一个参数flg代表当前查询的是哪棵线段树。

#include #include #include #include using namespace std;const int INF = 0x3f3f3f3f;const int maxn = 1e5;int n, q, date[maxn], segTree[2][maxn<<2];void pushup(int root) { segTree[0][root] = min(segTree[0][root<<1], segTree[0][root<<1|1]); segTree[1][root] = max(segTree[1][root<<1], segTree[1][root<<1|1]);}void build(int L, int R, int root) { if (L == R) { segTree[0][root] = segTree[1][root] = date[L]; return; } int mid = (L + R)>>1; build(L, mid, root<<1); build(mid + 1, R, root<<1|1); pushup(root);}int query(int L, int R, int root, int qL, int qR, int flag) { if (qL <= L && R <= qR) { return segTree[flag][root]; } int mid = (L + R)>>1; int temp = flag ? 0 : INF; if (qL <= mid) { int t = query(L, mid, root<<1, qL, qR, flag); if (flag) temp = max(temp, t); else temp = min(temp, t); } if (qR > mid) { int t = query(mid + 1, R, root<<1|1, qL, qR, flag); if (flag) temp = max(temp, t); else temp = min(temp, t); } return temp;}int main(){ while (scanf("%d %d", &n, &q) == 2) { for (int i = 1; i <= n; i++) { scanf("%d", &date[i]); } build(1, n, 1); int a, b; while (q--) { scanf("%d %d", &a, &b); printf("%d\n", query(1, n, 1, a, b, 1) - query(1, n, 1, a, b, 0)); } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。