得罪了一堆人的我发了X03 RMO 题解
2024-07-24 17:07:25
发布于：浙江
22阅读
0回复
0点赞
#include <bits/stdc++.h>
using namespace std;
int mx_f[500005][30];
int mi_f[500005][30];
int n,q,a[1000005];
void createmax() {
for (int i = 1;i <= n;i ++) mx_f[i][0] = a[i];
int k = log2(n); // 取q的最大值
for (int j = 1;j <= k;j ++) {
for (int i = 1;i <= n - (1 << j) + 1;i ++) {
mx_f[i][j] = max(mx_f[i][j-1],mx_f[i + (1 << j - 1)][j - 1]);
}
}
}
void createmin() {
for (int i = 1;i <= n;i ++) mi_f[i][0] = a[i];
int k = log2(n); // 取q的最大值
for (int j = 1;j <= k;j ++) {
for (int i = 1;i <= n - (1 << j) + 1;i ++) {
mi_f[i][j] = min(mi_f[i][j-1],mi_f[i + (1 << j - 1)][j - 1]);
}
}
}
int Queue(int l,int r) {
// 最大值与最小值返回差值
int k = log2(r - l + 1);
int mx = max(mx_f[l][k],mx_f[r - (1 << k) + 1][k]);
int mi = min(mi_f[l][k],mi_f[r - (1 << k) + 1][k]);
return mx - mi;
}
int main() {
cin >> n >> q;
for (int i = 1;i <= n;i ++) cin >> a[i];
createmax();
createmin();
while (q --) {
int l,r;
cin >> l >> r;
cout << Queue(l,r) << "\n";
}
return 0;
}
这里空空如也
有帮助，赞一个