0.概述

$\;Minimum/Maximum\;Query)$ 问题是指：对于长度为 $n$ 的数列 $A$ ，回答若干询问 $RMQ(A,i,j)(1\le i\le j\le n)$ ，返回数列 $A$ 中下标在 $[i, j]$ 里的最小（大）值，也就是说， $R M Q$ 问题是指求区间最值的问题。

所以我们要用 $\mathcal O(n)$ 的时间预处理、 $\mathcal O(1)$ 的时间在线查询（不支持修改）！

1. $\tt ST$ 表

用 $f (i, j)$ 表示 $i,i+2^j)$ 中的最小值，很明显有 $f(i,j+1)=\min[f(i,j),f(i+2^j,j)]$

所以这是一个 $\mathcal O(n\log n)$ 的递推，预处理 $\lfloor\log x\rfloor(x\le n)$ 之后便可以做到 $\mathcal O(1)$ 查询了。

温馨提示：这一部分是略讲的，因为大家平时都使用这种方法，RMQ标准算法 纯粹是作为一种学习罢了，在比赛中很难有时间打。

namespace STtable{
    // ST表	const int MaxN = 363640, LogN = 19;	int st[MaxN][LogN], duishu[MaxN], item[MaxN];	void init(const int shuzu[],int n){
   		for(int i=0; i<=n; ++i)			st[i][0] = i, item[i] = shuzu[i];		for(int j=1; (1<
   
    <=n; ++j)			for(int i=0; i+(1<
    
     <=n; ++i){
   				int &x = st[i][j] = st[i][j-1];				const int &y = st[i+(1<
     
      >1)][j-1];				if(item[y] < item[x]) x = y;			}		for(int i=2; i<=n+1; ++i)			duishu[i] = duishu[i>>1]+1;	}	int query(int l,int r){
   		if(l > r) swap(l,r);		int k = duishu[r-l+1];		const int &x = st[l][k];		const int &y = st[r-(1<

2.约束 $\tt RMQ$

所谓约束 $\tt RMQ$ 即是，对于欲查询的数列 $A$ 有 $\forall i\in[1,n),A_{i}-A_{i+1}\in\{1,-1\}$

1,−1}

其实，更广泛的，只要相邻两数之差（前者减后者）只能是两种值，都可以叫 约束RMQ 。

怎么做呢？分块。设定块的大小为 $m=\lfloor\frac{\log n}{2}\rfloor$ ，对于每一个块，可以求出最小值，然后将一块作为最小单位，利用 ST表 进行预处理。此处的复杂度是 $\mathcal O[\frac{n}{m}\log(\frac{n}{m})]=\mathcal O[\frac{n}{\log n}(\log n-\log m)]=\mathcal O(n)$ 的。

对于某一块中的“边角料”，如何处理？注意到某一块中的 差分数组 的不同的数量只有 $\mathcal O(2^m)=\mathcal O(2^{\frac{\log n}{2}})=\mathcal O(\sqrt{2^{\log n}})=\mathcal O(\sqrt n)$ ，所以枚举它，然后处理 每一个子区间。复杂度 $\mathcal O(m^2\sqrt n)=\mathcal O(\sqrt n\log^2n)\le \mathcal O(n)$ 。

然后就可以 $\mathcal O(1)$ 查询了。

namespace narrowRMQ{
    // 约束RMQ	const int MaxN = 4000000, block = 11;	int benzhi[1<
   
    >r&1) ++ now;					else if((-- now) < all)						id = r, all = now;					benzhi[S][l][r] = id;				}			}		for(int i=0; i<=n/block; ++i)			data[i] = infty;		for(int i=1; i<=n; ++i)			if(item[i] < data[i/block]){
   				data[i/block] = item[i];				best[i/block] = i;			}		STtable::init(data,n/block);	}	int query(int a,int b){
   		if(a > b) swap(a,b);		if(a == b) return a;		int l = a/block; a -= l*block;		int r = b/block; b -= r*block;		int L = inside[l], R = inside[r];		if(l == r) return benzhi[L][a+1][b]+l*block;		int res = 0, x = 0;		if(l+1 <= r-1){
   			x = STtable::query(l+1,r-1);			if(data[x] < item[res]) res = best[x];		}		x = a+l*block;		if(a != block-1)			x = benzhi[L][a+1][block-1]+l*block;		if(item[x] < item[res]) res = x;		x = b+r*block;		if(b != 0)			x = benzhi[R][1][b]+r*block;		if(item[x] < item[res]) res = x;		return res;	}}

3.笛卡尔树

笛卡尔树是一棵二叉树，包含了一个序列中的每个元素。对于每个元素在原序列中的下标来说，笛卡尔树是一棵二叉搜索树（即，中序遍历结果单调递增）；对于每个元素的大小来说，笛卡尔树是类似于堆的（子树中的最值恰好为子树的根）。

笛卡尔树的建树过程是 $\mathcal O(n)$ 的。利用笛卡尔树，在原序列上的 $\tt RMQ$ 问题 等价于笛卡尔树上的 $l c a$ 问题。因为 $l c a$ 恰好为最小值——这是由定义决定的。

namespace Descartes{
    // 笛卡尔树	const int MaxN = 2000000;	int son[MaxN|1][2], meet[MaxN<<1];	int depth[MaxN<<1], dfn;	int first[MaxN|1];	void dfs(int o,int deep=0){
   		meet[++ dfn] = o, depth[dfn] = deep;		first[o] = dfn; // 第一次见面		for(int i=0; i<2; ++i) if(son[o][i]){
   			dfs(son[o][i],deep+1);			meet[++ dfn] = o, depth[dfn] = deep;		}	}	void init(int shuzu[],int n){
   		static vector
   
     v; v.clear();		v.push_back(0), shuzu[0] = -infty;		for(int i=1,x=0; i<=n; v.push_back(i++)){
   			for(x=0; shuzu[v.back()]>shuzu[i]; )				x = v.back(), v.pop_back();			son[i][0] = x, son[v.back()][1] = i;		}		dfn = 0, dfs(son[0][1]);	}}

4. $\tt RMQ$ 求 $l c a$

$l c a$ 有一种广为人知的求解方法：对树进行一次 $\tt{dfs}$ ，在进入一个点、回溯到一个点的时候，都将这个点加入“访问序列”中。在 $x$ 第一次出现于访问序列中之后，在 $y$ 第一次出现于访问序列中之前， $l c a$ 会出现，并且没有比它深度更小的点。所以只需要在 “访问序列” 中找深度最小的点即可！不就是 $\tt RMQ$ 吗？更棒的是，它是 约束RMQ ！

这个转化过程显然是 $\mathcal O(n)$ 的，并且得到的访问序列也是 $\mathcal O(n)$ 的。

namespace normalRMQ{
   	void init(int shuzu[],int n){
   		Descartes::init(shuzu,n);		narrowRMQ::init(Descartes::depth,Descartes::dfn);	}	int query(int l,int r){
   		l = Descartes::first[l], r = Descartes::first[r];		return Descartes::meet[narrowRMQ::query(l,r)];	}}

5.例题

本来是单调队列的板题（你懂的）。

一时兴起，给你们看一个很有意思，但是复杂度没有保证的，也许复杂度在这道题里是有保证的，但是在一般的题目中，它的一次查询甚至可以达到 $\mathcal O(\log^2 n)$ 。

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;inline int readint() {
   	int a = 0; char c = getchar(), f = 1;	for(; c<'0' or c>'9'; c=getchar())		if(c == '-') f = -f;	for(; '0'<=c and c<='9'; c=getchar())		a = (a<<3)+(a<<1)+(c^48);	return a*f;}void writeint(int x){
   	if(x < 0) putchar('-'), x = -x;	if(x > 9) writeint(x/10);	putchar((x%10)^48);}# define MB template < typename T >MB void getMax(T &a,const T &b){
    if(a < b) a = b; }MB void getMin(T &a,const T &b){
    if(b < a) a = b; }const int infty = (1<<30)-1;namespace STtable{
    // ST表	const int MaxN = 363640, LogN = 19;	int st[MaxN][LogN], duishu[MaxN], item[MaxN];	void init(const int shuzu[],int n){
   		for(int i=0; i<=n; ++i)			st[i][0] = i, item[i] = shuzu[i];		for(int j=1; (1<
       
        <=n; ++j)			for(int i=0; i+(1<
        
         <=n; ++i){ int &x = st[i][j] = st[i][j-1]; const int &y = st[i+(1<
         
          >1)][j-1]; if(item[y] < item[x]) x = y; } for(int i=2; i<=n+1; ++i) duishu[i] = duishu[i>>1]+1; } int query(int l,int r){ if(l > r) swap(l,r); int k = duishu[r-l+1]; const int &x = st[l][k]; const int &y = st[r-(1<
          
           >r&1) ++ now; else if((-- now) < all) id = r, all = now; benzhi[S][l][r] = id; } } for(int i=0; i<=n/block; ++i) data[i] = infty; for(int i=1; i<=n; ++i) if(item[i] < data[i/block]){ data[i/block] = item[i]; best[i/block] = i; } STtable::init(data,n/block); } int query(int a,int b){ if(a > b) swap(a,b); if(a == b) return a; int l = a/block; a -= l*block; int r = b/block; b -= r*block; int L = inside[l], R = inside[r]; if(l == r) return benzhi[L][a+1][b]+l*block; int res = 0, x = 0; if(l+1 <= r-1){ x = STtable::query(l+1,r-1); if(data[x] < item[res]) res = best[x]; } x = a+l*block; if(a != block-1) x = benzhi[L][a+1][block-1]+l*block; if(item[x] < item[res]) res = x; x = b+r*block; if(b != 0) x = benzhi[R][1][b]+r*block; if(item[x] < item[res]) res = x; return res; }}namespace Descartes{ // 笛卡尔树 const int MaxN = 2000000; int son[MaxN|1][2], meet[MaxN<<1]; int depth[MaxN<<1], dfn; int first[MaxN|1]; void dfs(int o,int deep=0){ meet[++ dfn] = o, depth[dfn] = deep; first[o] = dfn; // 第一次见面 for(int i=0; i<2; ++i) if(son[o][i]){ dfs(son[o][i],deep+1); meet[++ dfn] = o, depth[dfn] = deep; } } void init(int shuzu[],int n){ static vector
           
             v; v.clear(); v.push_back(0), shuzu[0] = -infty; for(int i=1,x=0; i<=n; v.push_back(i++)){ for(x=0; shuzu[v.back()]>shuzu[i]; ) x = v.back(), v.pop_back(); son[i][0] = x, son[v.back()][1] = i; } dfn = 0, dfs(son[0][1]); }}namespace normalRMQ{ void init(int shuzu[],int n){ Descartes::init(shuzu,n); narrowRMQ::init(Descartes::depth,Descartes::dfn); } int query(int l,int r){ l = Descartes::first[l], r = Descartes::first[r]; return Descartes::meet[narrowRMQ::query(l,r)]; }}const int MaxN = 2000001;int a[MaxN], n, m;int main(){ // freopen("rmq.in","r",stdin); // freopen("rmq.out","w",stdout); n = readint(), m = readint(); for(int i=1; i<=n; ++i) a[i] = readint(); normalRMQ::init(a,n); putchar('0'), putchar('\n'); for(int i=2; i<=n; ++i){ int j = max(1,i-m); j = normalRMQ::query(j,i-1); writeint(a[j]), putchar('\n'); } return 0;}

6.链接

竟然把这个问题讲清楚了的，点名表扬！

还有，感觉是从 $j a v a$ 转行的？

7.吐槽

是不是我的道行 $[h \overset{e}{ˊ} n g]$ 太浅，见的太少？但是我确实没有在 $\text{C++}$ 中找到能够精确对应这一段 $j a v a$ 代码的：

abstract class class_name{
   	private static boolean[] some_data;	public static final void method_name(){
   		// do something ...	}}

抽象的目的是使其不能被实例化，仅成员方法被调用（且不能够被重写）。

虽然 $\text{C++}$ 中给出了 $\text{namespace}$ ，实现了无法实例化、不能重写，但是默认 $p u b l i c$ 了！肿么办？

如果用纯虚函数 virtual void method() = 0 ，子类可以将其补充完整啊……

总的来说，就是 $\text{C++}$ 没有 $f i n a l$ 的修饰，不能阻止子类的重写。令人头疼！

当然咯，这些话并不代表着两种编程语言的优劣，只是我这个小蒟蒻自己吐槽一下而已。

转载地址：http://xgvq.baihongyu.com/

你可能感兴趣的文章