注意:ST不可查询动态区间的最大值instead
线段树可以, But
在其他情况用 ST表 来查询
区间最大值是最优的选择!!
ST 全称为 $$ Sparse { } Table $$
$$ ST / RMQ $$
代码如下:
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e6;
int n,m;
int f[N][25], a[N];
int Log[N];
inline int read(){ //快读
char c = getchar();
int f = 1, x = 0;
while(!isdigit(c)){if(c == '-') f = -1; c = getchar();}
while(isdigit(c)){x = (x << 1) + (x << 3) + (c - '0'); c = getchar();}
return x * f;
}
inline void write(int a){ //快输
if(a < 0) putchar('-'), a = -a;
if(a >= 10) write(a / 10);
putchar(a % 10 + 48);
}
void init(){ // 预处理
for(register int i = 1;i <= n;i ++) f[i][0] = a[i];
for(register int j = 1;(1 << j) <= n;j ++)
for(register int i = 1; i + (1 << j - 1) <= n;i ++)
f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
for(register int i = 1;i <= n;i ++)
Log[i] = log2(i);
}
int query(int l, int r){ //查询操作
int k = Log[r - l + 1];
return max(f[l][k], f[r - (1 << k) + 1][k]);
}
int main(){
n = read(), m = read();
for(register int i = 1;i <= n;i ++) a[i] = read();
int l,r;
init();
while(m --){
l = read(), r = read();
write(query(l, r));
putchar('\n');
}
return 0;
}
还可以:查询区间最大差值
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e6, M = 5000;
int n,m;
int f_max[N][25], f_min[N][25], a[N];
int Log[N];
int read(){
char c = getchar();
int f = 1, x = 0;
while(!isdigit(c)){if(c == '-') f = -1; c = getchar();}
while(isdigit(c)){x = (x << 1) + (x << 3) + (c - '0'); c = getchar();}
return x * f;
}
inline void write(int a){
if(a < 0) putchar('-'), a = -a;
if(a >= 10) write(a / 10);
putchar(a % 10 + 48);
}
void init_max(){
for(register int i = 1;i <= n;i ++) f_max[i][0] = a[i];
for(register int j = 1;(1 << j) <= n;j ++)
for(register int i = 1; i + (1 << j - 1) <= n;i ++)
f_max[i][j] = max(f_max[i][j - 1], f_max[i + (1 << j - 1)][j - 1]);
for(register int i = 1;i <= n;i ++)
Log[i] = log2(i);
}
int query_max(int l, int r){
int k = Log[r - l + 1];
return max(f_max[l][k], f_max[r - (1 << k) + 1][k]);
}
void init_min(){
for(register int i = 1;i <= n;i ++) f_min[i][0] = a[i];
for(register int j = 1;(1 << j) <= n;j ++)
for(register int i = 1; i + (1 << j - 1) <= n;i ++)
f_min[i][j] = min(f_min[i][j - 1], f_min[i + (1 << j - 1)][j - 1]);
for(register int i = 1;i <= n;i ++)
Log[i] = log2(i);
}
int query_min(int l, int r){
int k = Log[r - l + 1];
return min(f_min[l][k], f_min[r - (1 << k) + 1][k]);
}
int main(){
n = read(), m = read();
for(register int i = 1;i <= n;i ++) a[i] = read();
int l,r;
init_max();
init_min();
while(m --){
l = read(), r = read();
write(query_max(l, r) - query_min(l, r));
putchar('\n');
}
return 0;
}
为啥要在int前面加个register呢??有啥用呢-----凑字数???/