Rmq
例一P2880 [USACO07JAN]平衡的阵容
一个RMQ裸题
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int rd(){
int x=0,fl=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(fl=='-')fl=-fl;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return fl*x;
}
int n,m;
ll mx[100100][25],mi[100100][25];
void RMQ(){
for(int j=1;(1<<j)<=n;j++)
for(int i=1;i+(1<<j)-1<=n;i++){
mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
mi[i][j]=min(mi[i][j-1],mi[i+(1<<(j-1))][j-1]);
}
}
ll ask(int l,int r){
int kk=log(r-l+1)/log(2);
int minn=min(mi[l][kk],mi[r-(1<<kk)+1][kk]);
int maxx=max(mx[l][kk],mx[r-(1<<kk)+1][kk]);
return maxx-minn;
}
int main(){
n=rd();m=rd();
for(int i=1;i<=n;i++)mi[i][0]=mx[i][0]=rd();
RMQ();
for(int i=1;i<=m;i++){
int l=rd(),r=rd();
if(l==r){printf("0\n");continue;}
printf("%lld\n",ask(l,r));
}
return 0;
}
例二UVa 11235 频繁出现的数值
给一个非降序排列的整数数组a
你的任务是对于一系列询问(i, j)，回答ai,ai+1…aj中次数出现最多的值所出现的次数。 分析：
由于数列是非降序的，所以所有相等的数都会聚集在一起。这样我们就可以把整个数组进行编码。
如-1,1,1,2,2,2,4就可以编码成(-1,1),(1,2),(2,3),(4,1)表示（a，b）数组中的a连续出现了b次。
用num[i]表示原数组下表是i的数在编码后的第num[i]段。left[i],right[i]表示第i段的左边界和右边界，用coun[i]表示第i段有conu[i]个相同的数。这样的话每次查询(L, R)就只要计算(right[L]-L+1),(R-left[R]+1)和RMQ(num[L]+1, num[R]-1)这三个值的最大值就可以了。 其中，RMQ是对coun数组进行取件查询的结果。 特殊的，如果L和R在同一个区间内的话，那么结果就是（R-L+1）
进阶版关于二维RMQ问题：
二维RMQ问题就是求一个矩阵N*M中的一个小块矩阵内的最值问题.
其中
dmin[i][j][ii][jj]=x 表示以(i, j)为左上角,以(i+(1<<ii)-1, j+(1<<jj)-1 )为右下角的矩阵内的最小值.dmax的值类似.
下面dmin[i][j][ii][jj]的值如何求呢?
首先我们知道 dmin[i][j][0][0]的值就是v[i][j],而假设dmin[i][j][ii][jj]中的ii不为0,那么dmin[i][j][ii][jj]= min(dmin[i][j][ii-1][jj], dmin[i+(1<<ii)][j][ii-1][jj] );如果ii为0,那么就按jj来求.
其实上面的求法就是等于把二维问题转变为一维问题来求解.
下面我们讨论如何查询结果.
对于一个以(x1, y1)为左上角,以(x2, y2)为右下角的矩形,如何求它的最小值和最大值呢?下面假设我们求最小值:
我们把(x1，y1)与(x2，y2)构成的矩形分成四小块，这四小块可能有重合部分，但是它们共同构成了目标矩形：
dmin[x1][y1][ii][jj]
dmin[x1][y2-(1<<jj)+1][ii][jj]
dmin[x2-(1<<ii)+1][y1][ii][jj]
dmin[x2-(1<<ii)+1][y2-(1<<jj)+1][ii][jj](自己想象下上面4小块是怎么样的？)
temp 1=min(dmin[x1][y1][ii][jj] , dmin[x1][y2-(1<<jj)+1][ii][jj])
temp 2=min(dmin[x2-(1<<ii)+1][y1][ii][jj] ,dmin[x2-(1<<ii)+1][y2-(1<<jj)+1][ii][jj] )
最终结果是min(temp1, temp2);