区间最值（RMQ）问题
RMQ 是英文 Range Maximum/Minimum Query 的缩写，表示区间最大（最小）值查询。
在笔者接下来的描述中，默认初始数组大小为 $n$，默认询问次数为 $m$。
在笔者接下来的描述中，默认时间复杂度标记方式为 $O(\mathrm{数据预处理}) \sim O(\mathrm{单次询问})$。
例题
| 名称 | 编号 | 备注 |
|---|---|---|
| 滑动窗口 /【模板】单调队列 | Luogu P1886 | $k,n \le 10^6$，每次询问 $[i,i+k-1](1 \le i \le i+k-1 \le n)$ 的最值 |
| 【模板】ST 表 | Luogu P3865 | $n \le 10^5,m \le 2 \times 10^5$ |
| 由乃救爷爷 | Luogu P3793 | $n,m \le 2 \times 10^7$，时限 $5 \mathrm{s}$ |
单调队列
时间复杂度 $O(n)$（只能用于题目“滑动窗口”）
空间复杂度 $O(n)$
单调栈
时间复杂度 $O(m\log m) \sim O(\log n)$
空间复杂度 $O(n)$
ST 表
时间复杂度 $O(n\log n) \sim O(1)$
空间复杂度 $O(n\log n)$
线段树
时间复杂度 $O(n) \sim O(\log n)$
空间复杂度 $O(n)$
Four Russian
原算法
Four Russian 是一个由四位俄罗斯籍的计算机科学家提出来的基于 ST 表的算法。
在 ST 表的基础上 Four Russian 算法对其做出的改进是序列分块。
具体来说，对于原数组 $A$，我们将每 $S$ 个数划分一块，总共有 $\lceil N/S \rceil$ 块。我们先预处理出每一块的最值，再在块的基础上建立 ST 表。同时，我们也在每一块内部建立 ST 表。
询问时，我们可以将询问区间划分为左边的零头、中间的若干块和右边的零头（当询问区间在同一块内时，直接在块内 ST 表求解即可）。
当 $S=\log n$ 时，预处理时间复杂度最优。
时间复杂度 $O(n\log \log n) \sim O(1)$
空间复杂度 $O(n\log \log n)$
改进
我们发现，在询问的两个端点在数组 A 中属于不同的块的时候，数组 A 中块内的询问是关于每一块前缀或者后缀的询问。
显然这些询问可以通过预处理答案在 $O(n)$ 的时间复杂度内被解决。
这样子我们只需要在询问的时候进行至多一次 ST 表上的查询操作了。
注意：当左右端点在同一块内时，本优化会假。但是出题人一般不会卡这个，因为这样可能会让暴力程序通过。
当 $S=\sqrt n$ 时，预处理时间复杂度最优。
时间复杂度 $O(n+\sqrt n \times \log n) \sim O(1)$
空间复杂度 $O(n+\sqrt n \times \log n)$
//Luogu P3793
#include<cstdio>
#include<cmath>
namespace GenHelper{
unsigned z1,z2,z3,z4,b;
unsigned rand_(){
b=((z1<<6)^z1)>>13;
z1=((z1&4294967294U)<<18)^b;
b=((z2<<2)^z2)>>27;
z2=((z2&4294967288U)<<2)^b;
b=((z3<<13)^z3)>>21;
z3=((z3&4294967280U)<<7)^b;
b=((z4<<3)^z4)>>12;
z4=((z4&4294967168U)<<13)^b;
return(z1^z2^z3^z4);
}
}
void srand(unsigned x){
using namespace GenHelper;
z1=x;
z2=(~x)^0x233333333U;
z3=x^0x1234598766U;
z4=(~x)+51;
}
int read(){
using namespace GenHelper;
int a=rand_()&32767;
int b=rand_()&32767;
return a*32768+b;
}
int max(int a,int b){
return a>b?a:b;
}
inline void swap(int&a,int&b){
int temp=a;
a=b;
b=temp;
}
const int maxn=20000005,sqrtn=50000;
int n,m,s,block;
int a[maxn],pre[maxn],suf[maxn],st[sqrtn][22];
int getpos(int x){
return(x+block-1)/block;
}
int bf(int l,int r){
int ans=a[l];
for(int i=l+1;i<=r;i++)ans=max(ans,a[i]);
return ans;
}
void init(){
int p=getpos(n);
register int len,i;
for(len=1;len<=20;len++)
for(i=1;i<=p-(1<<len)+1;i++)
st[i][len]=max(st[i][len-1],st[i+(1<<(len-1))][len-1]);
for(i=1;i<=n;i++)
if(i%block!=1)pre[i]=max(pre[i-1],a[i]);
else pre[i]=a[i];
for(i=n;i>=1;i--)
if(i%block)suf[i]=max(suf[i+1],a[i]);
else suf[i]=a[i];
}
int query(int l,int r){
int len=log2(r-l-1);
return max(st[l+1][len],st[r-(1<<len)][len]);
}
int main(){
register int i,j;
scanf("%d%d%d",&n,&m,&s);
srand(s);
block=sqrt(n);
for(i=1;i<=n;i++){
j=getpos(i);
a[i]=read();
st[j][0]=max(a[i],st[j][0]);
}
init();
int x,y,l,r,mx;
unsigned long long answer=0;
while(m--){
x=read()%n+1,y=read()%n+1;
if(x>y)swap(x,y);
l=getpos(x),r=getpos(y),mx=max(suf[x],pre[y]);
if(l==r)answer+=bf(x,y);
else if(r-l==1)answer+=mx;
else answer+=max(mx,query(l,r));
}
printf("%llu",answer);
return 0;
}