UOJT225 RMQ

かねき　けん · 2018-07-03 17:15:27 · 个人记录

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXN 50005
using namespace std;
typedef int I;

int N,Q,s1[MAXN],ans,xx,yy;

I read()
{
    I ans=0,f=1;
    char c=getchar();
    while(!isdigit(c))
    {
        if(c=='-')f=-1;c=getchar();
    }
    while(isdigit(c))
    {
        ans=ans*10+c-'0';c=getchar();
    }
    return ans*f;
}

void write(int a)
{
    if(!a)putchar('0');if(a<0)putchar('-'),a=-a;
    char b[15]={0},i;
    for(i=13;a;--i)b[i]=a%10+'0',a/=10;
    for(++i;i<14;++i)putchar(b[i]);
}

int minST[MAXN][20]; 

  void InitMinST(int a[], int n) 
  { 
      for(int i=0; i<=n; i++) 
          minST[i][0]=a[i]; 
      for(int j=1; (1<<j)<=n; j++) 
          for(int i=0; i+(1<<j)-1<=n; i++) 
              minST[i][j]=min(minST[i][j-1],minST[i+(1<<(j-1))][j-1]); 
  } 

  int RMQMIN(int s,int t)
   { 
    int k=(int)(log(t-s+1.0)/log(2.0)); 
    return min(minST[s][k],minST[t-(1<<k)+1][k]); 
  } 

int maxST[MAXN][20];

  void InitMaxST(int a[], int n) 
  { 
      for(int i=0; i<=n; i++) 
          maxST[i][0]=a[i]; 
      for(int j=1; (1<<j)<=n; j++) 
          for(int i=0; i+(1<<j)-1<=n; i++) 
              maxST[i][j]=max(maxST[i][j-1],maxST[i+(1<<(j-1))][j-1]); 
  } 

  int RMQMAX(int s,int t)
   { 
    int k=(int)(log(t-s+1.0)/log(2.0)); 
    return max(maxST[s][k],maxST[t-(1<<k)+1][k]); 
  } 

  int main()
  {
    I i,j;
    cin>>N>>Q;
    for(i=1;i<=N;i++)
    {
        s1[i]=read();

      }
      InitMinST(s1,N);
      InitMaxST(s1,N);

    while(Q--)
    {
        xx=read();
        yy=read();
        xx=RMQMAX(xx,yy)-RMQMIN(xx,yy);
        write(xx);putchar('\n');
      }

    return 0;
  }