View Code of Problem 2897

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define N 200222
int maxc[N][40],minc[N][40],a[N],n,m;
int ifmax(int a,int b)
{
        if(a>b)
                return a;
        return b;
}
int ifmin(int a,int b)
{
        if(a<b)
                return a;
        return b;
}
int logg(int x)
{
        int cnt=-1;
        while(x)
        {
                cnt++;
                x=x>>1;
        }
        return cnt;
}
void QWER()
{
        int i,j;
        for(i=1;i<=n;i++)
        {
                maxc[i][0]=a[i];
                minc[i][0]=a[i];
        }
        for(j=1;j<=logg(n);j++)
                for(i=1;i+(1<<j)-1<=n;i++)
        {
                maxc[i][j]=ifmax(maxc[i][j-1],maxc[i+(1<<(j-1))][j-1]);
                minc[i][j]=ifmin(minc[i][j-1],minc[i+(1<<(j-1))][j-1]);
        }
}
int main()
{
       // freopen("in","r",stdin);
        int i,da,di,x,y,k;
        while(scanf("%d%d",&n,&m)!=EOF)
        {
                memset(minc,1<<30,sizeof(minc));
                memset(maxc,-(1<<30),sizeof(maxc));
                for(i=1;i<=n;i++)
                        scanf("%d",&a[i]);
                QWER();
                for(i=0;i<m;i++)
                {
                        scanf("%d%d",&x,&y);
                        k=logg(y-x+1);
                        da=ifmax(maxc[x][k],maxc[y+1-(1<<(k))][k]);
                       di=ifmin(minc[x][k],minc[y+1-(1<<(k))][k]);
                        printf("%d\n",da-di);
                }
        }
        return 0;
}