poj3264.cpp

//#include <bits/stdc++.h>
#include <stdio.h>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <iostream>
#define PI 3.14159265
#define N 50000+5
#define ll long long
#define INF 2147483647
using namespace std;
int st[N][16],st2[N][16],g[N],n,u,v,m,k,maxj;//st[i][j]代表從i開始,長度為2^j的數組
void build(){
    for(int i=0;i<n;i++) st[i][0]=st2[i][0]=g[i];
    maxj=log2(n);
    for(int j=1;j<=maxj;j++)
        for(int i=0;i+(1<<j)-1<n;i++){
            st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);//記錄max 下面的數組塊 靠上面兩個數組塊得到
            st2[i][j]=min(st2[i][j-1],st2[i+(1<<(j-1))][j-1]);//記錄min
        }
}
int rmq(int u,int v,int id){
    k=log2(v-u+1);//區間長度取log 因為陣列表示2^j
    if(id) return max(st[u][k],st[v-(1<<k)+1][k]);//詢問區間u,v的最大最小值 相當於在數組u和數組v下面 再新增一塊數組塊
    return min(st2[u][k],st2[v-(1<<k)+1][k]);//v-(1<<k)+1為從v倒推回去 長度為2k的數組塊
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++) scanf("%d",&g[i]);
    build();
    while(m--){
        scanf("%d%d",&u,&v);
        printf("%d\n",rmq(u-1,v-1,1)-rmq(u-1,v-1,0));
    }
}