依舊是線段樹基礎題

詢問區(qū)間的最大值和最小值之差，只有詢問，沒有插入刪除。繼續(xù)理解基礎線段樹

?

#include <iostream> #include <algorithm> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <string> #include <vector> #include <set> #include <map> #include <queue> #include <stack> #include <climits>//形如INT_MAX一類的 #define MAX 50005 #define INF 0x7FFFFFFF #define REP(i,s,t) for(int i=(s);i<=(t);++i) #define ll long long #define mem(a,b) memset(a,b,sizeof(a)) #define mp(a,b) make_pair(a,b) #define L(x) x<<1 #define R(x) x<<1|1 # define eps 1e-5 //#pragma comment(linker, "/STACK:36777216") ///傳說中的外掛 using namespace std; struct node {int l,r,mid,max,min; }tree[4*MAX]; int hei[MAX],a,b; int maxx(int a,int b) {if(a > b) return a;return b; } int minn(int a,int b) {if(a < b) return a;return b; } void up(int num) {if(tree[num].max < tree[L(num)].max) tree[num].max = tree[L(num)].max;if(tree[num].max < tree[R(num)].max) tree[num].max = tree[R(num)].max;if(tree[num].min > tree[L(num)].min) tree[num].min = tree[L(num)].min;if(tree[num].min > tree[R(num)].min) tree[num].min = tree[R(num)].min; }void build(int l,int r,int num) {tree[num].l = l;tree[num].r = r;tree[num].mid = (l + r) >> 1;tree[num].max = 0;tree[num].min = INF;if(l == r) {tree[num].max = hei[l];tree[num].min = hei[l];return ;}build(l,tree[num].mid ,L(num));build(tree[num].mid+1,r,R(num));up(num); }void query(int l,int r,int num) {if(l <= tree[num].l && r >= tree[num].r) {a = maxx(a,tree[num].max);b = minn(b,tree[num].min);return ;}if(r <= tree[num].mid ) {query(l,r,L(num));}else if(l > tree[num].mid) {query(l,r,R(num));}else {query(l,tree[num].mid,L(num));query(tree[num].mid + 1,r,R(num));} }void test(int n) {for(int i=1; i<=2*n+1; i++){printf("l:%d r:%d max:%d min:%d\n",tree[i].l,tree[i].r,tree[i].max,tree[i].min);} }int main() {int n,q,i;int l,r;cin >> n >> q;for(i=1; i<=n; i++) {scanf("%d",&hei[i]);}build(1,n,1);//test(n);for(i=1; i<=q; i++) {a = 0;b = INF;scanf("%d%d",&l,&r);query(l,r,1);printf("%d\n",a - b);}return 0; }

?

?

轉載于:https://www.cnblogs.com/dyllove98/p/3201117.html

總結

以上是生活随笔為你收集整理的Poj 3246 Balanced Lineup（线段树基础）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。