NKLINEUP - Xếp hàng
Tác giả: skyvn97
Ngôn ngữ: C++
#include<stdio.h>
#define MAX 50505
int n,q;
int a,b;
int h[MAX];
int f[MAX][20];
int l[MAX][20];
int min(int x,int y) {
if (x<y) return (x); else return (y);
}
int max(int x,int y) {
if (x>y) return (x); else return (y);
}
void init(void) {
scanf("%d",&n);
scanf("%d",&q);
int i;
for (i=1;i<=n;i=i+1) scanf("%d",&h[i]);
}
void RMQ(void) {
int i,j;
for (i=1;i<=n;i=i+1) {
f[i][0]=h[i];
l[i][0]=h[i];
}
for (j=1;(1<<j)<=n;j=j+1)
for (i=1;i+(1<<j)-1<=n;i=i+1) {
f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
l[i][j]=min(l[i][j-1],l[i+(1<<(j-1))][j-1]);
}
}
int res(int a,int b) {
int k=0;
while ((1<<k)<=b-a+1) k=k+1;
k=k-1;
return (max(f[a][k],f[b-(1<<k)+1][k])-min(l[a][k],l[b-(1<<k)+1][k]));
}
void process(void) {
int i;
for (i=1;i<=q;i=i+1) {
scanf("%d",&a);
scanf("%d",&b);
printf("%d\n",res(a,b));
}
}
int main(void) {
init();
RMQ();
process();
}