RMQ 模板题 poj 3264

时间：2021-02-27 19:37:48

题目：点这里

题意：给一个长度n的数列，然后又Q个询问，问L   到R   中最大值与最小值的差。

分析：RMQ 的模板题。

代码：

#include<stdio.h>

#include<iostream>

#include<algorithm>

#include<string.h>

using namespace std;

const int max_=;

int minm,maxm;

int dp_max[max_][],dp_min[max_][];

int a[max_];

void RMQ_init(int n)

{

    for(int i=;i<=n;i++)

       dp_max[i][]=a[i],

       dp_min[i][]=a[i];

    for(int j=;(<<j)<=n;j++)

        for(int i=;i+(<<j)-<=n;i++)

    {

        dp_max[i][j]=max(dp_max[i][j-],dp_max[i+(<<(j-))][j-]);

        dp_min[i][j]=min(dp_min[i][j-],dp_min[i+(<<(j-))][j-]);

    }

}

void RMQ_Q(int L,int R)

{

    int k=;

    while((<<(k+))<=R-L+)k++;

    minm=min(dp_min[L][k],dp_min[R+-(<<k)][k]);

    maxm=max(dp_max[L][k],dp_max[R+-(<<k)][k]);

}

int main()

{

    int n,m;

  scanf("%d %d",&n,&m);

        for(int i=;i<=n;i++)

           scanf("%d",&a[i]);

        RMQ_init(n);

        while(m--)

        {

            int l,r;

            cin>>l>>r;

            RMQ_Q(l,r);

           printf("%d\n",maxm-minm);

        }

}

用  cin  和cout  会超时……

相关文章