Giveyouanumbersequence,canyoutellmebetweenthei-thnumberandthej-thnumber,whichisthemaximumandwhichistheminimum?InputThefirstlineoftheinputisNandQ.N(N<2^17)isthenumberofintegersandQ(Q<2^17)isthenumberofqu

Question

Give you a number sequence,can you tell me between the i-th number and the j-th number,which is the maximum and which is the minimum?
Input
The first line of the input is N and Q.N(N< 2^17) is the number of integers and Q(Q < 2^17) is the number of querys.The second line is the N integers and the following Q lines include two integers i and j(i

Answer 1

区间最值RMQ
ST算法或者线段树
提供一个ST代码
/*
Range Minimum Query
Sparse Table (ST) algorithm
*/
#include
#include
#define min(x,y) (x)(y)?(x):(y)
#define N 100005
int n,s[N],dp[N][25],MAX[N][25],MIN[N][25];
void slove()//psotion
{
int i,j;
for(i=0;i