学步园

题意：

给出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;
}

继续继续。