pku 3264 source.cpp

PKU3264 lineup代码 RMQ 的ST算法

// PKU 3264 Source 

#include<iostream>
#include<fstream>
#include<cmath>

using namespace std;
int a[500010];
int *d[26][500010];
int *d2[26][500010];
inline int *min(int *a,int *b) {
    if (*a<*b) return a;
    else return b;
}
inline int *max(int *a,int *b) {
    if (*a<*b) return b;
    else return a;
}
void make_RMQ(int n) {
   int i,j;
   for (i=1;i<=n;i++) {d[0][i]=&a[i];d2[0][i]=&a[i];}  
   for (j=1;j<=int(log((double)n)/log(2.));j++) 
	   for(i=1;i+(1<<j)-1<=n;i++) 
	   {d[j][i]=min(d[j-1][i],d[j-1][i+(1<<(j-1))]);
        d2[j][i]=max(d2[j-1][i],d2[j-1][i+(1<<(j-1))]);}
   return;
}

int *RMQmin(int i,int j) {
    int k=int(log((double)(j-i+1))/log(2.));
    return min(d[k][i],d[k][j-(1<<k)+1]);
}

int *RMQmax(int i,int j) {
    int k=int(log((double)(j-i+1))/log(2.));
    return max(d2[k][i],d2[k][j-(1<<k)+1]);
}

/*
int main() {
    freopen("a.in","r",stdin);freopen("a.out","w",stdout);
    int n,i;
    scanf("%d",&n);
    for (i=1;i<=n;i++) scanf("%d",&a[i]);
    make_RMQ(n);
    int *k=RMQ(5,5);
    cout<<*k<<endl;
    return 0;
}
*/
int main()
{
 //   freopen("input.in","r",stdin);
    int n,q,i;
    scanf("%d%d",&n,&q);
    for (i=1;i<=n;i++) scanf("%d",&a[i]);
    make_RMQ(n);


	for(i=1;i<=q;i++){
		int b,e;
		scanf("%d%d",&b,&e);
		int *k=RMQmax(b,e);
		int *k2=RMQmin(b,e);
		printf("%d\n",*k-*k2);
	}

	return 0;
}