poj 3264 线段树 寻找最大最小值 SEGMENT TREE

本文主要是介绍poj 3264 线段树 寻找最大最小值 SEGMENT TREE，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

Input

Output

Sample Input

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

Sample Output

6
3
0

Source

My original code is lengthy:

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
int N,Q,cows[50001],A,B;
int cal(int a,int b){int max=cows[a],min=cows[a];for(int i=a+1;i<=b;i++){if(max<cows[i])max=cows[i];if(min>cows[i])min=cows[i];}return max-min;
}
struct node{int l,r,min,max;   
}tree[50001*3];
struct maxmin{int max,min;
};void build(int k,int l,int r){tree[k].l=l;tree[k].r=r;    if( l==r ){tree[k].max=max(cows[l],cows[r]);tree[k].min=min(cows[l],cows[r]);}else{build(2*k+1,l,(l+r)/2);build(2*k+2,(l+r)/2+1,r);tree[k].max=max(tree[2*k+1].max,tree[2*k+2].max);tree[k].min=min(tree[2*k+1].min,tree[2*k+2].min);                }
}
int query(int k,int l,int r,int *Max,int *Min){int max1,max2,min1,min2;if(tree[k].l==l && tree[k].r==r){(*Max)=tree[k].max;(*Min)=tree[k].min;return (*Max)-(*Min);}int mid=(tree[k].l+tree[k].r)/2;if( r<=mid ){query(2*k+1,l,r,Max,Min);return (*Max)-(*Min);}else if( l>=mid+1 ){query(2*k+2,l,r,Max,Min);return (*Max)-(*Min);}else{query(2*k+1,l,mid,Max,Min);max1=(*Max);min1=(*Min);query(2*k+2,mid+1,r,Max,Min);max2=(*Max);min2=(*Min);(*Max)=max(max1,max2);(*Min)=min(min1,min2);return (*Max)-(*Min);        }}
int main(){int i,j,Max,Min;scanf("%d%d",&N,&Q);for(i=1;i<=N;i++)scanf("%d",&cows[i]);build(0,1,N);for(i=0;i<Q;i++){scanf("%d%d",&A,&B);int res=query( 0,A,B,&Max,&Min );printf("%d\n",res);}//system("pause");return 0; 
}

The concise code :

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
int N,Q,cows[50001],A,B;struct node{int l, r, min, max;   
}tree[50001 * 3];
int maxx, minx;void build(int k, int l, int r){tree[k].l=l;tree[k].r=r;    if( l==r )tree[k].max=tree[k].min=cows[l];else{build(2 * k + 1, l, (l + r) / 2);build(2 * k + 2, (l + r) / 2 + 1, r);tree[k].max = max(tree[2*k+1].max, tree[2*k+2].max);tree[k].min = min(tree[2*k+1].min, tree[2*k+2].min);                }
}
int query(int k, int l, int r){int max1, max2, min1, min2;    if(tree[k].l == l && tree[k].r == r){maxx = tree[k].max;minx = tree[k].min;return (maxx - minx);}    int mid = (tree[k].l + tree[k].r) / 2;if(r <= mid){query(2 * k + 1, l, r);return (maxx - minx);}else if(l >= mid + 1){query(2 * k + 2, l, r);return (maxx - minx);}else{query(2 * k + 1, l, mid);max1 = maxx;min1 = minx;query(2 * k + 2, mid + 1, r);    maxx = max(max1, maxx);minx = min(min1, minx);return maxx - minx;        }}
int main(){int i,j,Max,Min;scanf("%d%d",&N,&Q);for(i=1;i<=N;i++)scanf("%d",&cows[i]);build(0,1,N);for(i=0;i<Q;i++){scanf("%d%d",&A,&B);int res=query(0,A,B);printf("%d\n",res);}//system("pause");return 0; 
}

Another way:

Use the RMQ to get the maximum and minimum of d[i][j]:

//8200K    1610MS
#include
#include
const int M = 50005;
const int N = 20;
int H,dx[M][N],dy[M][N],n;
int max (int a,int b)
{return a > b ? a : b;
}
int min(int a,int b)
{return a > b ? b : a;
}
void Init()
{int i,j;for (i = 1; i <= n; i ++){scanf ("%d",&H);dx[i][0] = dy[i][0] = H;}for (j = 1; (1<<j) <= n; j ++)for (i = 1; i +(1<<j)-1<=n; i ++){dx[i][j] = min(dx[i][j-1],dx[i+(1<<(j-1))][j-1]);dy[i][j] = max(dy[i][j-1],dy[i+(1<<(j-1))][j-1]);}}
int RMQ(int L ,int R)
{int k = 0;while ((1<<(k+1))<=R-L+1) k ++;return max(dy[L][k],dy[R-(1<<k)+1][k]) - min(dx[L][k],dx[R-(1<<k)+1][k]);
}
int main ()
{int m,a,b;while (~scanf ("%d%d",&n,&m)){Init();while (m --){scanf ("%d%d",&a,&b);printf ("%d\n",RMQ(a,b));}}return 0;
}

A better concise version:

#include <stdio.h>
#include <vector>
#include <iostream>
using namespace std;class Node {public:int l, r, max, min;Node(int ll = 0, int rr = 0, int max1 = 0, int min1 = 0) : l(ll), r(rr), max(max1), min(min1){}
};void build(vector<Node>& tree, const vector<int>& height, int k, int l, int r) {tree[k].l = l, tree[k].r = r;if (l == r) {tree[k].max = tree[k].min = height[l];return;}build(tree, height, k*2+1, l, (l+r)/2);build(tree, height, k*2+2, (l+r)/2+1, r);tree[k].max = max(tree[k*2+1].max, tree[k*2+2].max);tree[k].min = min(tree[k*2+1].min, tree[k*2+2].min); 
}
int query(vector<Node>& tree, int k, int l, int r, int& maxv, int& minv) {int max1, min1, max2, min2;if (l == tree[k].l && r == tree[k].r) {maxv = tree[k].max, minv = tree[k].min;return maxv - minv;}int mid = (tree[k].l + tree[k].r) / 2;if (r <= mid) {return query(tree, k*2+1, l, r, maxv, minv);}else if (l >= mid+1) {return query(tree, k*2+2, l, r, maxv, minv);}else {query(tree, k*2+1, l, mid, max1, min1);query(tree, k*2+2, mid+1, r, max2, min2);   maxv = max(max1, max2);minv = min(min1, min2);return maxv -minv;}  
}
int main() {int N, Q, l, r, maxv, minv;scanf("%d%d", &N, &Q);vector<int> height(N,0);vector<Node> tree(50001 * 3);for (int i = 0; i < N; ++i)scanf("%d", &height[i]);build(tree, height, 0, 0, N-1);for (int i = 0; i < Q; ++i) {scanf("%d%d", &l, &r);printf("%d\n", query(tree, 0, l-1, r-1, maxv, minv));}return 0;
}

这篇关于poj 3264 线段树 寻找最大最小值 SEGMENT TREE的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---