效率至上(sdut3302) +线段树

Problem Description

题意很简单,给出一个数目为n的非有序序列,然后有m次查询.对于每次查询输入两个正整数l,r请输出区间[l,r]的最大值与最小值的差值

Input

第一行:输入两个正整数n,m    (1<=n<=50000,  1<=m<=200000  );

第二行:输入n个整数  大小范围为[1,100000];

接下来的m行,每次两个正整数l,r (1<=l<=r<=n);

Output

输出区间[l,r]最大值与最小值的差值.

Example Input

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

Example Output

6 3 0
求区间内最大值最小值的差,故用线段树;
线段树fish学长推荐的博客:http://www.cnblogs.com/TenosDoIt/p/3453089.html#f

#include <stdio.h>
#include <stdlib.h>

struct node
{
    long long int mindata,maxdata;
}tree[200000];
int max(int a,int b)
{
    if(a>b)return a;
    else return b;
}
int min(int a,int b)
{
    if(a>b)return b;
    else return a;
}
void build(int root,int l,int r)
{
    if(l==r)//l,r相等时说明达到叶子节点,可以存数了
    {
        scanf("%lld",&tree[root].mindata);
        tree[root].maxdata=tree[root].mindata;
        return;
    }
    int mid=(l+r)/2;//中值
    build(2*root,l,mid);//左半端,root也要到左节点
    build(2*root+1,mid+1,r);//同上
    tree[root].maxdata=max(tree[2*root].maxdata,tree[2*root+1].maxdata);//返回后更新根节点数据
    tree[root].mindata=min(tree[2*root].mindata,tree[2*root+1].mindata);//同上
}
long long int qmax(int l,int r,int root,int l1,int r1)
{
    if(l<=l1&&r>=r1)
    return tree[root].maxdata;
    int mid=(l1+r1)/2;
    int red=-100055;
    if(l<=mid)
        red=max(red,qmax(l,r,2*root,l1,mid));
    if(r>mid)
        red=max(red,qmax(l,r,2*root+1,mid+1,r1));
    return red;
}
long long int qmin(int l,int r,int root,int l1,int r1)
{
    if(l<=l1&&r>=r1)
    return tree[root].mindata;
    int mid=(l1+r1)/2;
    int red=100055;
    if(l<=mid)
        red=min(red,qmin(l,r,2*root,l1,mid));
    if(r>mid)
        red=min(red,qmin(l,r,2*root+1,mid+1,r1));
    return red;
}
int main()
{
    int n,m,l,r;
    scanf("%d %d",&n,&m);
    build(1,1,n);
    while(m--)
    {
        scanf("%d%d",&l,&r);
        printf("%lld\n",qmax(l,r,1,1,n)-qmin(l,r,1,1,n));
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注