题意:
给出N个数M个询问,每个询问一个区间(a,b)。输出区间内最大值最小值的差值。
思路:
线段树,也可以RMQ。
#include <iostream> #include <cstdio> #include <algorithm> #include <string> #include <cmath> #include <cstring> #include <queue> #include <set> #include <vector> #include <stack> #include <map> #include <iomanip> #define PI acos(-1.0) #define Max 50005 #define inf 1<<28 using namespace std; struct kdq { int l,r; int max,min;//存最大值最小值 } tree[Max*4]; int n,m; int cow[Max]; void build_tree(int l,int r,int u)//建树 { tree[u].l=l,tree[u].r=r; if(l==r) { tree[u].min=cow[l]; tree[u].max=cow[l]; return ; } int mid=(l+r)/2; build_tree(l,mid,u<<1); build_tree(mid+1,r,(u<<1)+1); tree[u].max=max(tree[u<<1].max,tree[(u<<1)+1].max);//更新最大值 tree[u].min=min(tree[u<<1].min,tree[(u<<1)+1].min);//更新最小值 } int querymax(int left,int right,int u)//寻找最大值 { if(tree[u].l==left&&tree[u].r==right) return tree[u].max; int mid=(tree[u].l+tree[u].r)/2; if(right<=mid)//插到左子树 return querymax(left,right,u<<1); else if(left>mid)//插到右子树 return querymax(left,right,(u<<1)+1); else return max(querymax(left,mid,u<<1),querymax(mid+1,right,(u<<1)+1)); } int querymin(int left,int right,int u)//寻找最小值 { if(tree[u].l==left&&tree[u].r==right) return tree[u].min; int mid=(tree[u].l+tree[u].r)/2; if(right<=mid) return querymin(left,right,u<<1); else if(left>mid) return querymin(left,right,(u<<1)+1); else return min(querymin(left,mid,u<<1),querymin(mid+1,right,(u<<1)+1)); } int main() { int a,b; cin>>n>>m; for(int i=1; i<=n; i++) scanf("%d",&cow[i]); build_tree(1,n,1); while(m--) { scanf("%d%d",&a,&b); int max1=querymax(a,b,1); int min1=querymin(a,b,1); printf("%d\n",max1-min1); } return 0; }
继续继续。