RMQ 问题：
给定一个序列，并有一些询问，每次询问一个区间的最大值或最小值。
下面以区间最大值为例进行讲解，设序列长度为 \(N\)，有 \(M\) 次查询。
1 单调队列
前提条件
每个查询的区间互相不包含、离线、不能进行修改、不能在序列中增加元素。
思路
将所有查询按左端点排序（如果不保证左端点递增，则不用），由于互相不包含，此时右端点也递增。剩下就是单调队列的模板。
时间复杂度为 \(\mathcal{O}(N+Q \log Q)\)。如果保证左端点递增，则 \(\mathcal{O}(N+Q)\)。
代码
#include<cstdio>
#define UP(i,a,b) for(i=a;i<=(b);++i)
#define DN(i,a,b) for(i=a;i>=(b);--i)
const int N=2e6+5;
int a[N],n,m;
template<typename T>
class queue{
private:
T a[N],*h,*t;
public:
queue():h(a),t(a){}
void push(T k){
*t=k;++t;
}
void pop_back(){
--t;
}
void pop_front(){
++h;
}
T back(){
return *(t-1);
}
T front(){
return *h;
}
bool size(){
return h!=t;
}
};
queue<int> q;
int main(){
int i;
scanf("%d%d",&n,&m);
UP(i,1,n){
scanf("%d",a+i);
}
printf("0\n");
UP(i,1,n-1){
while(q.size()&&a[q.back()]>a[i]){
q.pop_back();
}
while(q.size()&&q.front()<=i-m){
q.pop_front();
}
q.push(i);
printf("%d\n",a[q.front()]);
}
return 0;
}
2 ST 表
前提条件
不能进行修改、不能在序列中增加元素。
思路
预处理出序列的 ST 表，然后进行查询。
时间复杂度为 \(\mathcal(O)(N \log N+Q)\)。
代码
#include<cstdio>
#include<algorithm>
#define UP(i,a,b) for(i=a;i<=(b);++i)
#define DN(i,a,b) for(i=a;i>=(b);--i)
using std::max;
const int N=1e6+5;
int dp[N][25],log_2[N];
int query(int l,int r){
int k=log_2[r-l+1];
return max(dp[l][k],dp[r-(1<<k)+1][k]);
}
int main(){
int n,m,i,j,l,r;
scanf("%d%d",&n,&m);
UP(i,1,n){
scanf("%d",&dp[i][0]);
if(i>1){
log_2[i]=log_2[i>>1]+1;
}
}
UP(j,1,log_2[n]){
UP(i,1,n-(1<<j)+1){
dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}
}
while(m--){
scanf("%d%d",&l,&r);
printf("%d\n",query(l,r));
}
return 0;
}
3 线段树
前提条件
不能在序列中增加元素。
思路
线段树向上维护区间最值即可，其他与线段树的模板相同。
时间复杂度为 \(\mathcal{O}((N+Q) \log N)\)。
例题
给定长度为 \(N\) 区间和 \(M\) 次查询，查询的格式为：
\(1,l,r,k\)：将 \([l,r]\) 区间的所有数都加 \(k\)。
\(2,l,r\)：求区间 \([l,r]\) 的最大值。
代码
#include<cstdio>
#include<algorithm>
#define UP(i,a,b) for(i=a;i<=(b);++i)
#define DN(i,a,b) for(i=a;i>=(b);--i)
using std::max;
const int N=1e5+5;
int a[N],n,m;
struct node{
int t,lz;
}t[N<<2];
int ls(int p){
return p<<1;
}
int rs(int p){
return p<<1|1;
}
void push_up(int p){
t[p].t=max(t[ls(p)].t,t[rs(p)].t);
}
void build(int p=1,int l=1,int r=n){
int mid=(l+r)>>1;
if(l==r){
t[p].t=a[l];t[p].lz=0;
return;
}
build(ls(p),l,mid);
build(rs(p),mid+1,r);
push_up(p);
}
void tag(int k,int p,int l,int r){
t[p].t+=(r-l+1)*k;
t[p].lz+=k;
}
void push_down(int p,int l,int r){
int mid=(l+r)>>1;
if(t[p].lz){
tag(t[p].lz,ls(p),l,mid);
tag(t[p].lz,rs(p),mid+1,r);
t[p].lz=0;
}
}
void update(int x,int y,int k,int p=1,int l=1,int r=n){
int mid=(l+r)>>1;
if(x<=l&&r<=y){
tag(k,p,l,r);
return;
}
push_down(p,l,r);
if(x<=mid){
update(x,y,k,ls(p),l,mid);
}
if(mid<y){
update(x,y,k,rs(p),mid+1,r);
}
push_up(p);
}
int query(int x,int y,int p=1,int l=1,int r=n){
int mid=(l+r)>>1,res=0;
if(x<=l&&r<=y){
return t[p].t;
}
push_down(p,l,r);
if(x<=mid){
res=max(res,query(x,y,ls(p),l,mid));
}
if(mid<y){
res=max(res,query(x,y,rs(p),mid+1,r));
}
return res;
}
int main(){
int i,o,l,r,k;
scanf("%d%d",&n,&m);
UP(i,1,n){
scanf("%d",a+i);
}
build();
UP(i,1,m){
scanf("%d%d%d",&o,&l,&r);
if(o==1){
scanf("%d",&k);
update(l,r,k);
}else{
printf("%d\n",query(l,r));
}
}
return 0;
}
4 平衡树
前提条件
无前提条件。
思路
用平衡树实现线段树。因为平衡树可以插入结点，所以还可以在序列中插入元素。
时间复杂度为 \(\mathcal{O}((N+Q) \log N)\)。
这里用 Splay 树实现。
例题
给定长度为 \(N\) 区间和 \(M\) 次查询，查询的格式为：
\(1,l,r,k\)：将 \([l,r]\) 区间的所有数都加 \(k\)。
\(2,x,y\)：将 \([x,len]\) 中的所有元素都后移一位，并在第 \(x\) 位插入元素 \(y\)。
\(3,x\)：删除第 \(x\) 个数。
\(4,l,r\)：求区间 \([l,r]\) 的最大值。
代码