2024-07-27 15:23:47
发布于：湖南
30阅读
0回复
0点赞
求区间最值的神器
你以为我会跟你讲？
直接亮代码
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int a[200005], st1[25][200005], st2[25][200005], st3[25][200005];
int read(){
char c = getchar();
int x = 0, f = 1;
while(!isdigit(c)){
if(c == '-') f = -f;
c = getchar();
}
while(isdigit(c)){
x = (x << 3) + (x << 1) + c - '0';
c = getchar();
}
return x * f;
}
void _write(int n){
if(n == 0) return;
_write(n / 10);
putchar(n % 10 + '0');
}
void write(int n, bool end = 0){
if(n < 0) putchar('-'), _write(-n);
else if(n == 0) putchar('0');
else _write(n);
if(end) putchar('\n');
}
int main(){
int n = read(), m = read();
for(int i = 1; i <= n; i++){
st1[0][i] = st2[0][i] = st3[0][i] = a[i] = read();
}
for(int i = 1; (1 << i) <= n; i++){
for(int j = 1; j <= n - (1 << i) + 1; j++){
st1[i][j] = max(st1[i - 1][j], st1[i - 1][j + (1 << i >> 1)]);
st2[i][j] = min(st2[i - 1][j], st2[i - 1][j + (1 << i >> 1)]);
st3[i][j] = __gcd(st3[i - 1][j], st3[i - 1][j + (1 << i >> 1)]);
}
}
int k, l, r;
while(m--){
k = read(), l = read(), r = read();
int len = r - l + 1;
int i = log2(len);
if(k == 1) write(max(st1[i][l], st1[i][r - (1 << i) + 1]), 1);
if(k == 2) write(min(st2[i][l], st2[i][r - (1 << i) + 1]), 1);
if(k == 3) write(__gcd(st3[i][l], st3[i][r - (1 << i) + 1]), 1);
}
return 0;
}
有帮助，赞一个