题目描述
静态维护区间最大值与最小值的差
样例
输入
6 3
1
7
3
4
2
5
1 5
4 6
2 2
输出
6
3
0
思路
我们可以分别维护区间最大值,区间的最小值,
分别记为$max_st[i][j],min_st[i][j]$
照着st表的板子打一遍就好
注意
查询的时候右区间要记得+1,否则右面的那个区间可能会越界,到不属于这个区间的外面去
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=50010;
const int M=16;
int max_st[N][M];
int min_st[N][M];
int n,q;
int a[N];
void init()
{
for(int i=1;i<=n;i++)
min_st[i][0]=a[i],max_st[i][0]=a[i];
for(int j=1;(1<<j)<=n;j++)
for(int i=1;i+(1<<j)-1<=n;i++)
{
min_st[i][j]=min(min_st[i][j-1],min_st[i+(1<<j-1)][j-1]);
max_st[i][j]=max(max_st[i][j-1],max_st[i+(1<<j-1)][j-1]);
}
}
int max_quary(int l,int r)
{
int k=0;
while(l+(1<<k+1)-1<=r)
k++;
return max(max_st[l][k],max_st[r-(1<<k)+1][k]);
}
int min_quary(int l,int r)
{
int k=0;
while(l+(1<<k+1)-1<=r)
k++;
return min(min_st[l][k],min_st[r-(1<<k)+1][k]);
}
int main()
{
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
init();
for(int i=1;i<=q;i++)
{
int l,r;
scanf("%d%d",&l,&r);
printf("%d\n",max_quary(l,r)-min_quary(l,r));
}
return 0;
}