临时
2025-12-28 11:54:29
发布于：北京
2阅读
0回复
0点赞
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e4 + 10;
int st1[N][68]; //最大值
int st2[N][68]; //最小值
int a[N]; //原数据
int n; //数据的数量
int q;
void createST(){
//0列初始化
for(int i = 1;i <= n;i++){
st1[i][0] = a[i];
st2[i][0] = a[i];
}
int k = log2(n);
//按列计算
for(int j = 1;j <= k;j++){
for(int i = 1;i + (1 << j) - 1 <= n;i++){
st1[i][j] = max(st1[i][j - 1],st1[i + (1 << (j - 1))][j - 1]);
//计算最小值
st2[i][j] = max(st2[i][j - 1],st2[i + (1 << (j - 1))][j - 1]);
}
}
}
int query(int L,int R){
int k = log2(R - L + 1); //长度的指数次幂
//计算最大值
int mx = max(st1[L][k],st1[R - (1 << k) + 1][k]);
//计算最小值
int mi = min(st2[L][k],st2[R - (1 << k) + 1][k]);
//返回最大减去最小
return mx - mi;
}
signed main(){
cin >> n;
for(int i = 1;i <= n;i++){
cin >> a[i];
}
createST();
for(int i = 1;i <= q;i++){
int L,R;
cin >> L >> R;
cout << query(L,R) << "\n";
}
return 0;
}
这里空空如也
有帮助，赞一个