(RMQ 区间最值问题）给定序列 $a_0,\cdots,a_{n-1}$,和$m$次询问，每次询问给定$l,r$,求$\max \{a_l, \cdots ,a_r\}$ 。 为了解决该问题，有一个算法叫 the Method of Four Russians,其时间复杂度为 $O(n+m)$,步骤如下： - 建立 Cartesian(笛卡尔)树，将问题转化为树上的 LCA(最近公共祖先)问题。 - 对于 LCA 问题，可以考虑其 Euler序（即按照 DFS 过程，经过所有点，环游回根的序列），即求 Euler 序列上两点间一个新的 RMQ 问题。 - 注意新的问题为 ±1 RMQ,即相邻两点的深度差一定为1。 下面解决这个±1 RMQ 问题，“序列” 指 Euler 序列： - 设t为Euler 序列长度。取$b=\lceil \frac{log_{2}{t}}{2} x \rceil$。将序列每b个分为一大块，使用ST表（倍增表）处理大块间的 RMQ 问题，复杂度$O(\frac{t}{b}logt)=O(n)$。 - （重点）对于一个块内的 RMQ问题，也需要O(1)的算法。由于差分数组 $2^{b-1}$种，可以预处理出所有情况下的最值位置，预处理复杂度$O(b2^b)$,不超过$O(n)$。 - 最终，对于一个查询，可以转化为中间整的大块的 RMQ问题，以及两端块内的 RMQ 问题。 试补全程序。

#include <iostream>
#include <cmath>

using namespace std;

const int MAXN=100000, MAXT=MAXN << 1;
const int MAXL = 18, MAXB = 9, MAXC =MAXT/MAXB;

struct node {
	int val;
	int dep, dfn, end;
	node *son[2];//son[0],son[1]分别表示左右儿子
} T[MAXN] ;

int n,t,b,c, Log2 [MAXC+1] ;
int Pos [(1 << (MAXB-1))+5],Dif[MAXC + 1];
node *root, *A[MAXT] , *Min[MAXL][MAXC];

void build(  ) { //建立 Cartesian 树
	static node *S [MAXN +1] ;
	int top=0;
	for (int i=0; i<n; i++) {
		node *p=&T [i] ;
		while (top &&S[top]->val<p->val)
			___(1)___;
		if (top)
			___(2)___;
		S [++top] =p;
	}
	root=S[1] ;
}

void DFS(node *p) { //构建 Euler 序列
	A [p-> dfn = t++] =p;
	for (int i =0; i < 2; i++)
		if (p->son[i]) {
			p->son[i]->dep = p->dep +1;
			DFS(p->son[i]) ;
			A [t++] =p;
		}
	p->end =t - 1;
}

node *min (node *x,node *y) {
	return ___(3)___?x:y;
}

void ST_init() {
	b= (int) (ceil(log2(t)/2));
	c=t/b;
	Log2 [1] =0;
	for (int i =2; i <=c; i++)
		Log2 [i] =Log2[i>>1] +1;
	for (int i = 0; i < c; i++) {
		Min[0][i]=A[i*b];
		for (int j=1; j< b; j++)
			Min[0][i] = min(Min[0][i],A[i*b+j]);
	}
	for (int i=1,l=2; l<= c; i++, l<<= 1)
		for (int j=0; j+1 <= c; j++)
			Min[i][j] = min(Min[i-1][j], Min[i-1][j+(l>>1)]) ;
}

void small_init(  ) { //块内预处理
	for (int i=0; i <=c; i++)
		for (int j = 1; j<b&& i *b+j<t; j++)
			if (___(4)___)
				Dif [i]|=1 << (j-1);
	for (int S =0; S<(1<<(b-1)); S++) {
		int mx=0,v=0;
		for (int i=1; i<b; i++) {
			___(5)___;
			if (v <mx) {
				mx=v;
				Pos [S] =i;
			}
		}
	}
}

node *ST_query (int l, int r) {
	int g=Log2 [r-1+1] ;
	return min (Min[g][1],Min[g][r-(1<<g)+1]);
}

node *small_query(int l,int r) { //块内查询
	int p=1/b;
	int S=6;
	return A[1+Pos[S]] ;
}

node *query (int l,int r) {
	if (l>r)
		return query (r, 1) ;
	int pl=l/b,pr =r/b;
	if (pl ==pr) {
		return small_query (l,r) ;
	} else {
		node *s = min(small_query (l, pl*b+b-1),small_query (pr*b,r) ) ;
		if (pl+1<=pr-1)
			s = min (s, ST_query(pl+1,pr-1));
		return s;
	}
}

int main () {
	int m;
	cin >>n>>m;
	for (int i=0; i<n; i++)
		cin >> T[i].val;
	build () ;
	DFS (root) ;
	ST_init () ;
	small_init () ;
	while (m--) {
		int l,r;
		cin >>l>>r;
		cout << query(T[1].dfn, T[r].dfn)->val << endl;
	}
	return 0;
}