学步园

题目

一个线段树的水题。

用RMQ水了一个。

时间比线段树快乐将近0.5s，但空间大了很多

线段树代码如下：

/*
     Memroy 2740K
     Time 4016Ms
*/

#include<iostream>
#include<cstdio>
using namespace std;
#define maxn 50005
#define lson rt<<1
#define rson rt<<1|1

struct Tree
{
    int l,r;
    int mx,mn;
}tree[maxn<<2];

void PushUp(int rt)
{
    tree[rt].mx=max(tree[lson].mx,tree[rson].mx);
    tree[rt].mn=min(tree[lson].mn,tree[rson].mn);
}

void build(int l,int r, int rt)
{
    tree[rt].l=l;
    tree[rt].r=r;
    if(l==r){
        scanf("%d",&tree[rt].mx);
        tree[rt].mn=tree[rt].mx;
        return ;
    }

    int m=(l+r)>>1;
    build(l,m,lson);
    build(m+1,r,rson);
    PushUp(rt);
}

int query_mx(int x,int y,int rt)
{
    int l,r;
    l=tree[rt].l;
    r=tree[rt].r;
    if(l==x&&r==y){
        return tree[rt].mx;
    }

    int m=(l+r)>>1,ans=0;
    if(x<=m)  ans=max(ans,query_mx(x,min(m,y),lson));
    if(y>m) ans=max(ans,query_mx(max(m+1,x),y,rson));
    return ans;
}

int query_mn(int x,int y,int rt)
{
    int l,r;
    l=tree[rt].l;
    r=tree[rt].r;
    if(l==x&&r==y){
        return tree[rt].mn;
    }

    int m=(l+r)>>1,ans= 1000000;
    if(x<=m)  ans=min(ans,query_mn(x,min(m,y),lson));
    if(y>m) ans=min(ans,query_mn(max(m+1,x),y,rson));
    return ans;
}

int main()
{
    int m,n,a,b;
    while(~scanf("%d%d",&n,&m)){
        build(1,n,1);
        while(m--){
            scanf("%d%d",&a,&b);
            printf("%d\n",query_mx(a,b,1)-query_mn(a,b,1));
        }
    }
    return 0;
}

RMQ的代码如下：

/*
    Memory 16560K
    Time 3563ms
*/

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
#define maxn  50005

int dp1[maxn][40];
int dp2[maxn][40];

int a[maxn],n,m;

void RMQ_init1()
{
    for(int i=1;i<=n;i++) dp1[i][0]=a[i];
    for(int j=1;j<=log((double)n)/log(2.0);j++)
      for(int i=1;i+(1<<j)-1<=n;i++)
        dp1[i][j]=min(dp1[i][j-1],dp1[i+(1<<(j-1))][j-1]);
}

void RMQ_init2()
{
    for(int i=1;i<=n;i++) dp2[i][0]=a[i];
    for(int j=1;j<=log((double)n)/log(2.0);j++)
      for(int i=1;i+(1<<j)-1<=n;i++)
        dp2[i][j]=max(dp2[i][j-1],dp2[i+(1<<(j-1))][j-1]);
}

int RMQ1(int l,int r)
{
    int k=0;
    while((1<<(k+1))<=r-l+1) k++;
    return min(dp1[l][k],dp1[r-(1<<k)+1][k]);
}

int RMQ2(int l,int r)
{
     int k=0;
    while((1<<(k+1))<=r-l+1) k++;
    return max(dp2[l][k],dp2[r-(1<<k)+1][k]);
}

int main()
{
    while(~scanf("%d%d",&n,&m)){
        for(int i=1;i<=n;i++)
          scanf("%d",&a[i]);
        RMQ_init1();
        RMQ_init2();
        while(m--){
            int a,b;
            scanf("%d%d",&a,&b);
            printf("%d\n",RMQ2(a,b)-RMQ1(a,b));
        }
    }
    return 0;
}