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();
}

Download