题目描述

本题很简单，给定n,然后输入n个整数，然后给定m，输入m个询问，对于每个询问，求区间[a, b]内最大值与最小值的差值。

估计很多同学看完就想到可以用万能的线段树在解此题了，不过罗老师告诉大家，对于此类问题，还有一个叫RMQ的方法哦!

当然不管用什么方法，希望你先把它解决了吧！

输入

输入n, m

接下来n行，每行输入一个整数vi

接下来m行，每行输入两个整数a,b，表示询问[a, b]

输出

对于每组询问，求区间[a, b]内，最大值与最小值的差值。

样例输入

6 3
1
7
3
4
2
5
1 5
4 6
2 2

样例输出

6
3
0

提示

1<=N<=50000, 1<=m<=100000, 0<=vi<=1000000

思路

可以用倍增的思路,F[i][j]表示从i开始,长度为$2^j$的区间内的最大值

查询时,只需要找到两个较小的区间合并即可

代码

#include <bits/stdc++.h>
using namespace std;

int n,m,l,r,a[50005],f[50005][18],ff[50005][18];

void initf(){
    for (int i=1;i<=n;++i) f[i][0]=a[i];
    int t=log(n)/log(2);
    for (int j=1;j<=t;++j){
        for (int i=1;i<=n-(1<<j)+1;++i){
            f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        }
    }
}

void initff(){
    for (int i=1;i<=n;++i) ff[i][0]=a[i];
    int t=log(n)/log(2);
    for (int j=1;j<=t;++j){
        for (int i=1;i<=n-(1<<j)+1;++i){
            ff[i][j]=max(ff[i][j-1],ff[i+(1<<(j-1))][j-1]);
        }
    }
}

int getf(int l,int r){
    int len=r-l+1;
    int tmp=log(len)/log(2);
    return min(f[l][tmp],f[r-(1<<tmp)+1][tmp]);
}

int getff(int l,int r){
    int len=r-l+1;
    int tmp=log(len)/log(2);
    return max(ff[l][tmp],ff[r-(1<<tmp)+1][tmp]);
}

int main(){
    cin>>n>>m;
    for (int i=1;i<=n;++i) scanf("%d",&a[i]);
    initf();
    initff();
    for (int i=1;i<=m;++i){
        scanf("%d %d",&l,&r);
        if (l>r) swap(l,r);
        printf("%d\n",getff(l,r)-getf(l,r));
    }
    return 0;
}

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/66/