182. [USACO Jan07] 均衡队形

★★ 输入文件：lineup.in 输出文件：lineup.out 简单对比
时间限制：4 s 内存限制：128 MB

题目描述

农夫约翰的 N (1 ≤ N ≤ 50,000) 头奶牛，每天挤奶时总会按同样的顺序站好。一日，农夫约翰决定为奶牛们举行一个“终极飞盘”比赛。为简化问题，他将从奶牛队列中选出一个连续区间来进行游戏。不过，参加游戏的奶牛要玩的开心的话就不能在身高上差距太大。

农夫约翰制定了 Q (1 ≤ Q ≤ 200,000) 个预定的参赛组，给出它们的身高 (1 ≤ 身高 ≤ 1,000,000)。对每个参赛组，他需要你帮助确定组中最高牛和最低牛的身高差。

输入格式

第 1 行: 两个空格隔开的整数，N 和 Q。
第 2..N+1 行: 第 i+1 行包含一个整数表示第 i 头牛的身高。
第 N+2..N+Q+1 行: 两个整数 A 和 B(1 ≤ A ≤ B ≤ N)，表示一个从 A 到 B 的参赛组区间。

输出格式

第 1..Q 行: 每行包含一个整数来表示区间上最大身高差。

样例输入

样例输出

刚感觉是没有修改的线段树，扫一眼左栏有人说st表，感觉自己智障了....

//

//  main.cpp

//  cogs182

//

//  Created by Candy on 10/9/16.

//  Copyright © 2016 Candy. All rights reserved.

//

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cmath>

using namespace std;

typedef long long ll;

const int N=1e5+,MOD=1e9+;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x;

}

int n,q,a[N],l,r;

int mx[N][],mn[N][];

void initRMQ(){

    for(int i=;i<=n;i++) mx[i][]=mn[i][]=a[i];

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

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

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

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

        }

}

int qmx(int l,int r){

    int k=log(r-l+)/log();

    return max(mx[l][k],mx[r-(<<k)+][k]);

}

int qmn(int l,int r){

    int k=log(r-l+)/log();

    return min(mn[l][k],mn[r-(<<k)+][k]);

}

int main(int argc, const char * argv[]){

    freopen("lineup.in","r",stdin);

    freopen("lineup.out","w",stdout);

    n=read();q=read();

    for(int i=;i<=n;i++) a[i]=read();

    initRMQ();

    for(int i=;i<=q;i++){

        l=read();r=read();

        printf("%d\n",qmx(l,r)-qmn(l,r));

    }

    return ;

}