NYOJ_119_兵士が敵を殺す(三)

RMQ問題:典型的なSTアルゴリズムで通過できる.

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<string>

#include<queue>

using namespace std;

#define MAXN 100010  

int maxsum[MAXN][18],minsum[MAXN][18],n;

void RMQ()

{

    for(int j=1;(1<<j)<=n;++j)

        for(int i=1;i+(1<<j)-1<=n;++i)

        {

                maxsum[i][j]=max(maxsum[i][j-1],maxsum[i+(1<<(j-1))][j-1]);

                minsum[i][j]=min(minsum[i][j-1],minsum[i+(1<<(j-1))][j-1]);

        }

}

int main()

{

   int i,query,L,R;

   while(~scanf("%d%d",&n,&query))

   {

       for(int i=1;i<=n;++i)

       {

           scanf("%d",&maxsum[i][0]);

           minsum[i][0]=maxsum[i][0];

       }

       RMQ();

       while(query--)

       {

           scanf("%d%d",&L,&R);

           int k=(int)((log(R-L+1))/log(2.0)); 

           int minval=min(minsum[L][k],minsum[R-(1<<k)+1][k]);

           int maxval=max(maxsum[L][k],maxsum[R-(1<<k)+1][k]);

           printf("%d
",maxval-minval);

       }

   }

   return 0;

}