效率至上

梦里梦外; 2022-07-12 06:40 100阅读 0赞

#### 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 5

4 6

2 2

#### Example Output ####

#include<stdio.h>
    #include<stdlib.h>
    #define maxn 200010
    #define lson l,m,rt*2
    #define rson m+1,r,rt*2+1
    
    int sum[maxn];
    int max[maxn];
    int min[maxn];
    int mx=-1,mn=0x3f3f3f;
    
    int qmax(int a,int b)
    {
        return (a>b?a:b);
    }
    
    int qmin(int a,int b)
    {
        return (a>b?b:a);
    }
    
    void pushup (int rt)
    {
        sum[rt]=sum[rt*2]+sum[rt*2+1];
        max[rt]=qmax(max[rt*2],max[rt*2+1]);
        min[rt]=qmin(min[rt*2],min[rt*2+1]);
    }
    
    void build (int l,int r,int rt)
    {
        int m;
        if(l==r)
        {
            scanf("%d",&sum[rt]);
            max[rt]=min[rt]=sum[rt];
            return ;
        }
        m=(l+r)/2;
        build(lson);
        build(rson);
        pushup(rt);
    }
    
    void max_min(int L,int R,int l,int r,int rt)
    {
        int m;
        if(L<=l&&R>=r)
        {
            if(max[rt]>mx)
                mx=max[rt];
            if(min[rt]<mn)
                mn=min[rt];
            return ;
        }
        m=(l+r)/2;
        if(L<=m)
            max_min(L,R,lson);
        if(R>m)
            max_min(L,R,rson);
    }
    
    int main()
    {
        int n,m,i;
        int L,R;
        scanf("%d%d",&n,&m);
        build(1,n,1);
        while(m--)
        {
            scanf("%d%d",&L,&R);
            max_min(L,R,1,n,1);
            printf("%d\n",mx-mn);
            mx=-1;
            mn=0x3f3f3f;
        }
        return 0;
    }