效率至上

灰太狼 2022-08-18 02:29 76阅读 0赞

## 效率至上 ##

##### Time Limit: 5000ms Memory limit: 65536K 有疑问？点这里^\_^ #####

## 题目描述 ##

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

## 输入 ##

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

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

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

## 输出 ##

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

## 示例输入 ##

6 31734251 54 62 2

## 示例输出 ##

630

## 提示 ##

## 来源 ##

## 示例程序 ##

#include<iostream>  
    #include<stdio.h>  
    #include<algorithm>  
    #include<string.h>  
    #include<stdlib.h>  
    using namespace std;  
    int mn[51000][50];  
    int mx[51000][50];  
    int ls[51000];  
    int n, m;  
    void RMQ_min()  
    {  
        int i, j;  
        for( i = 1; i <= n; i++)  
            mn[i][0] = ls[i];  
        for(j = 1; (1<<j) <= n; j++)  
            for(i = 1; i+(1<<j)-1<=n;i++)  
              mn[i][j] = min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);  
    }  
    void RMQ_max()  
    {  
        int i, j;  
        for( i = 1; i <= n; i++)  
            mx[i][0] = ls[i];  
        for(j = 1; (1<<j) <= n; j++)  
            for(i = 1; i+(1<<j)-1<= n;i++)  
              mx[i][j] = max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);  
    }  
    int RN(int l,int r)  
    {  
        int k = 0;  
        while(1<<(k+1) <= r-l+1)  
            k++;  
        return min(mn[l][k],mn[r-(1<<k)+1][k]);  
    }  
    int RX(int l,int r)  
    {  
        int k = 0;  
        while(1<<(k+1) <= r-l+1)  
            k++;  
        return max(mx[l][k],mx[r-(1<<k)+1][k]);  
    }  
    int main()  
    {  
      
        while(~scanf("%d%d",&n,&m))  
        {  
            memset(mn,0,sizeof(mn));  
            memset(mx,0,sizeof(mx));  
           int i;  
           for(i = 1; i <= n; i++)  
                scanf("%d",&ls[i]);  
            RMQ_min();  
            RMQ_max();  
            int l, r;  
            for(i = 0; i < m; i++)  
            {  
                scanf("%d%d",&l,&r);  
                printf("%d\n",RX(l,r)-RN(l,r));  
            }  
        }  
        return 0;  
    }