CDOJ-1591（2017 UESTC Training for Graph Theory -A）

客官°小女子只卖身不卖艺 2022-06-13 08:23 162阅读 0赞

# A - An easy problem A #

##### Time Limit: 1000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others) #####

Submit   Status

N个数排成一列，Q个询问，每次询问一段区间内的数的极差是多少。

## Input ##

第一行两个整数N(1≤N≤50000),Q(1≤Q≤200000)。接下来一行N个整数a1 a2 a3 ....an,(1≤ai≤1000000000)。接下来Q行，每行两个整数L,R(1≤L≤R≤N)。

## Output ##

对于每个询问输出一行，一个整数表示区间内的极差。

## Sample input and output ##

<table style="border-spacing:0px; border-collapse:collapse; background-color:transparent; width:1534.55px; max-width:100%; margin-bottom:20px; border:1px solid rgb(221,221,221)"> 
 <thead style=""> 
  <tr style=""> 
   <th style="padding:8px; text-align:left; line-height:1.42857; vertical-align:bottom; border-width:0px 1px 2px; border-top-style:initial; border-top-color:initial; border-bottom-style:solid; border-bottom-color:rgb(221,221,221); border-right-style:solid; border-left-style:solid; border-right-color:rgb(221,221,221); border-left-color:rgb(221,221,221); width:767.273px"> Sample Input</th> 
   <th style="padding:8px; text-align:left; line-height:1.42857; vertical-align:bottom; border-width:0px 1px 2px; border-top-style:initial; border-top-color:initial; border-bottom-style:solid; border-bottom-color:rgb(221,221,221); border-right-style:solid; border-left-style:solid; border-right-color:rgb(221,221,221); border-left-color:rgb(221,221,221); width:766.364px"> Sample Output</th> 
  </tr> 
 </thead> 
 <tbody style=""> 
  <tr style=""> 
   <td style="padding:8px; line-height:1.42857; vertical-align:top; border:1px solid rgb(221,221,221)"> <pre style="overflow:auto; font-family:&quot;Source Code Pro&quot;,Monaco,Menlo,Consolas,&quot;Courier New&quot;,monospace; font-size:13px; padding:0px; margin-top:0px; margin-bottom:0px; line-height:1.42857; color:rgb(51,51,51); word-break:break-all; word-wrap:break-word; background-color:transparent; border:0px; white-space:pre-wrap">5 3
3 2 7 9 10
1 5
2 3
3 5</pre> </td> 
   <td style="padding:8px; line-height:1.42857; vertical-align:top; border:1px solid rgb(221,221,221)"> <pre style="overflow:auto; font-family:&quot;Source Code Pro&quot;,Monaco,Menlo,Consolas,&quot;Courier New&quot;,monospace; font-size:13px; padding:0px; margin-top:0px; margin-bottom:0px; line-height:1.42857; color:rgb(51,51,51); word-break:break-all; word-wrap:break-word; background-color:transparent; border:0px; white-space:pre-wrap">8
5
3</pre> </td> 
  </tr> 
 </tbody> 
</table>

题目大意：如题，询问区间最大值减最小值

题目思路：这题只要去维护区间的最值，可以用线段树，分块，简单点的是RMQ

AC代码：

#include<bits/stdc++.h>
    using namespace std;
    const int maxn = 5e4+100;
    int dpMin[maxn][20],dpMax[maxn][20];
    int a[maxn];
    int n,q;
    
    void RMQ()
    {
        for(int i=1;i<=n;i++)
            dpMin[i][0] = dpMax[i][0] = a[i];
    
        for (int j=1;j<=log(n)/log(2);j++)
        {
            for(int i=1;i<=n;i++)
            {
                if (i+(1<<j)-1<=n)
                {
                    dpMin[i][j]=min(dpMin[i][j-1],dpMin[i+(1<<(j-1))][j-1]);
                    dpMax[i][j]=max(dpMax[i][j-1],dpMax[i+(1<<(j-1))][j-1]);
                }
            }
        }
    }
    
    int getMin(int l,int r)
    {
        int k=log(r-l+1)/log(2.0);
        return min(dpMin[l][k],dpMin[r-(1<<k)+1][k]);
    }
    
    int getMax(int l,int r)
    {
        int k=log(r-l+1)/log(2.0);
        return max(dpMax[l][k],dpMax[r-(1<<k)+1][k]);
    }
    
    int main()
    {
        cin>>n>>q;
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        RMQ();
        while(q--)
        {
            int l,r;scanf("%d%d",&l,&r);
            printf("%d\n",getMax(l,r)-getMin(l,r));
        }
        return 0;
    }