//============================================================================
// Name        :
// Author      :
// Version     :
// Copyright   : 2014-1-24
// Description : RMQ
//============================================================================

#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <iomanip>
#include <bitset>
#include <list>
#include <ctime>
using namespace std ;

#define SET(arr, what)  memset(arr, what, sizeof(arr))
#define FF(i, a)        for(int i=1; i<a; i++)
#define SD(a)           scanf("%d", &a)
#define SSD(a, b)       scanf("%d%d", &a, &b)
#define SF(a)           scanf("%lf", &a)
#define SS(a)           scanf("%s", a)
#define SLD(a)          scanf("%lld", &a)
#define PF(a)           printf("%d\n", a)
#define PPF(a, b)       printf("%d %d\n", a, b)
#define SZ(arr)         (int)a.size()
#define SWAP(a,b)       a=a xor b;b= a xor b;a=a xor b;
#define read            freopen("in.txt", "r", stdin)
#define write           freopen("out.txt", "w", stdout)
#define MAX             1<<30
#define ESP             1e-5
#define lson            l, m, rt<<1
#define rson            m+1, r, rt<<1|1
template<class T> inline T sqr(T a){return a*a;}
template<class T> inline void AMin(T &a,T b){if(a>b)a=b;}
template<class T> inline void AMax(T &a,T b){if(a<b)a=b;}
template<class T> inline T Min(T a,T b){return a>b?b:a;}
template<class T> inline T Max(T a,T b){return a>b?a:b;}
const int maxn = 50000 + 10 ;
const int maxm = 100;

int N,Q,height[maxm],maxST[maxn][maxm],minST[maxn][maxm];

// //elements are numbered from 1 to n
// int RMQ_init_Max(int A[],int n)
// {
//     for(int i = 1 ; i <= n ; i++)
//         maxST[i][0] = A[i];
//     for(int j = 1 ; (1<<j)<=n ; j++)
//         for (int i = 1; i+(1<<j)-1<=n; i++)
//         maxST[i][j] = Max(maxST[i][j-1],maxST[i+(1<<(j-1))][j-1]);
//     return 0;
// }

// int RMQ_Max(int L , int R)
// {
//     int k = 0;
//     while((1<<(k+1))<=R-L+1) k++;//if 2^(k+1) <= R-L + 1,then k++.
//     return Max(maxST[L][k],maxST[R-(1<<k)+1][k]);
// }


// //elements are numbered from 1 to n
// int RMQ_init_Min(int A[],int n)
// {
//     for(int i = 1 ; i <= n ; i++)
//         minST[i][0] = A[i];
//     for(int j = 1 ; (1<<j)<=n ; j++)
//         for (int i = 1; i+(1<<j)-1<=n; i++)
//         minST[i][j] = Min(minST[i][j-1],minST[i+(1<<(j-1))][j-1]);
//     return 0;
// }

// int RMQ_Min(int L , int R)
// {
//     int k = 0;
//     while((1<<(k+1))<=R-L+1) k++;//if 2^(k+1) <= R-L + 1,then k++.
//     return Min(minST[L][k],minST[R-(1<<k)+1][k]);
// }

//elements are numbered from 1 to n
int RMQ_init(int A[],int n)
{
    for(int i = 1 ; i <= n ; i++)
    {
        maxST[i][0] = A[i];
        minST[i][0] = A[i];
    }
    for(int j = 1 ; (1<<j)<=n ; j++)
    {
        for (int i = 1; i+(1<<j)-1<=n; i++)
        {
        	maxST[i][j] = Max(maxST[i][j-1],maxST[i+(1<<(j-1))][j-1]);
        	minST[i][j] = Min(minST[i][j-1],minST[i+(1<<(j-1))][j-1]);
        }
    }
    return 0;
}

int RMQ_Max(int L , int R)
{
    int k = 0;
    while((1<<(k+1))<=R-L+1) k++;//if 2^(k+1) <= R-L + 1,then k++.
    return Max(maxST[L][k],maxST[R-(1<<k)+1][k]);
}


int RMQ_Min(int L , int R)
{
    int k = 0;
    while((1<<(k+1))<=R-L+1) k++;//if 2^(k+1) <= R-L + 1,then k++.
    return Min(minST[L][k],minST[R-(1<<k)+1][k]);
}


int main(int argc, char const *argv[])
{
	int l,r;
	SSD(N, Q);
	FF(i,N+1) SD(height[i]);
	RMQ_init(height,N);
	while(Q--)
	{
		SSD(l, r);
		//PPF(l, r);
		//if(l!=r)
		PF(RMQ_Max(l, r)-RMQ_Min(l,r));
		//else
		//	PF(0);
	}	
	return 0;
}

• Re:究竟错在哪了？ (4189) wxl777 2018-08-27 19:03:41