之前一直在用别人写的线性 \(\text{RMQ}\) 板子，但是我自己一直不会写。
所以去年退役以后，有一天学文化课的过程中走神想了这个。
不过现在这个东西是不是人人都会呢……
下面是我的想法，不过很久以前就已经被发明过了。
本来这玩意儿不值得发一篇博客的，但毕竟已经从文化课中解放了，想要发点什么庆祝一下……
-
把序列按照 \(\log n\) 分块，求出每一块的 \(\min\)。这部分 \(O(n)\)
-
对块建一个 \(\text{ST}\) 表，这部分 \(O(t\log t)\)，其中 \(t=\frac{n}{\log n}\)
-
对于每个块内，我们利用位运算实现一个单调栈，记录扫描到每个位置时这个栈的形态。由于位运算和变量赋值都看作 \(O(1)\)，这部分也可以做到线性。
-
查询的时候，对于两端点的散块我们利用预处理的单调栈求 \(\min\)，中间的整块用预处理的 \(\text{ST}\) 表就可以了。
下面是一个洛谷模板题 AC 代码。写得比较丑，跑得很慢，仅供参考。感觉最优解前几的写法都挺好看的。
#include<cstdio>
#include<iostream>
#define lg(x) (31-__builtin_clz(x))
#define llg(x) (63-__builtin_clz(x))
#define lowbit(x) ((x)&(-(x)))
const int INF=1e9+7;
int n,m;
int Max(int a,int b){return a>b?a:b;}
int Min(int a,int b){return a<b?a:b;}
struct RMQ{
static const int N=500086,B=20;
int n,mn[N/B][B],st[N],w[N];
#define gb(x) ((x-1)/B+1)
#define gs(l,r) (((1<<(r)+1)-1)^((1<<l)-1))
int& operator [](int x){return w[x];}
bool build(int sz){
n=sz;for(int i=1;i<=gb(n);i++)mn[i][0]=INF;
for(int i=1;i<=n;i++)mn[gb(i)][0]=Min(mn[gb(i)][0],w[i]);
for(int i=1;i<=gb(n);i++)
for(int j=1;(1<<j)<=i;j++)
mn[i][j]=Min(mn[i][j-1],mn[i-(1<<(j-1))][j-1]);
for(int i=1;i<=gb(n);i++){
int hp=(i-1)*B,stk=0;
for(int j=1;j<=B&&hp+j<=n;j++){
while(stk&&w[hp+lg(stk)]>w[hp+j])stk^=(1<<lg(stk));
st[hp+j]=(stk^=(1<<j));
}
}
return true;
}
int query(int l,int r){
int r1=INF,r2=INF,hl=B*(gb(l)-1),hr=B*(gb(r)-1);
if(hl==hr)return w[hl+lg(lowbit(st[r]&gs(l-hl,r-hr)))];
r1=Min(w[hr+lg(lowbit(st[r]))],w[hl+lg(lowbit(st[hl+B]&gs(l-hl,B)))]);
if(gb(l)+1<gb(r)){int lo=lg(gb(r)-gb(l)-1);r2=Min(mn[gb(r)-1][lo],mn[gb(l)+(1<<lo)][lo]);}
return Min(r1,r2);
}
}stl;
int read(){
int nn=0,ssss=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')ssss*=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){nn=nn*10+(ch-'0');ch=getchar();}
return nn*ssss;
}
int main(){
n=read();m=read();for(int i=1;i<=n;i++)stl[i]=-read();stl.build(n);
for(int i=1;i<=m;i++){int l=read();int r=read();std::cout<<-stl.query(l,r)<<'\n';}
}