题意：
给出每个位置奶牛高度，求出l,r这个区间段最高牛和最低的牛的差值
思路：
线段树维护最值
#include <stdio.h> #include <algorithm> #include <cstring> #include <iostream> using namespace std; const int maxn= 50005; const int inf=0x3f3f3f3f; int a[maxn]; struct node { int left,right,maxx,minn,num; }tree[4*maxn]; void Build(int i,int left,int right) { tree[i].left=left,tree[i].right=right; if(left==right) { tree[i].num=a[ tree[i].left ]; tree[i].minn=tree[i].num; tree[i].maxx=tree[i].num; return ; } int mid=(tree[i].left+tree[i].right)>>1; Build(i<<1,left,mid); Build(i<<1|1,mid+1,right); tree[i].minn=min(tree[i<<1].minn,tree[i<<1|1].minn); tree[i].maxx=max(tree[i<<1].maxx,tree[i<<1|1].maxx); return ; } int ansmax,ansmin; void query(int i,int left,int right) { if(tree[i].right==right&&tree[i].left==left) { ansmax=max(ansmax,tree[i].maxx); ansmin=min(ansmin,tree[i].minn); return ; } int mid=(tree[i].left+tree[i].right)>>1; if(left>mid) { query(i<<1|1,left,right); } else if(right<=mid) { query(i<<1,left,right); } else { query(i<<1,left,mid); query(i<<1|1,mid+1,right); } return ; } int main() { int n,q; scanf("%d%d",&n,&q); for(int i=1;i<=n;i++) scanf("%d",&a[i]); Build(1,1,n); while(q--) { int l,r; scanf("%d%d",&l,&r); ansmax=0,ansmin=inf; query(1,l,r); printf("%d\n",ansmax-ansmin); } }
