给定 n 个正整数 a1,a2,...,an 。 接下来有 m 次询问,第 i 次询问给出三个正整数 opti,li,ri ,如果 opt=1 则输出 ali,ali+1,...,ari 中的最小值;如果 opt=2 则输出 ali,ali+1,...,ari 中的最大值。c++
时间: 2023-11-14 22:04:24 浏览: 59
好的,以下是基于线段树的代码实现:
```cpp
#include <iostream>
#include <cstdio>
#include <climits>
using namespace std;
const int MAXN = 1e5 + 5;
struct Node {
int l, r;
int minVal, maxVal;
} segTree[MAXN * 4];
int a[MAXN];
// 建立线段树
void build(int p, int l, int r) {
segTree[p].l = l;
segTree[p].r = r;
if (l == r) {
segTree[p].minVal = segTree[p].maxVal = a[l];
return;
}
int mid = (l + r) / 2;
build(p * 2, l, mid);
build(p * 2 + 1, mid + 1, r);
segTree[p].minVal = min(segTree[p * 2].minVal, segTree[p * 2 + 1].minVal);
segTree[p].maxVal = max(segTree[p * 2].maxVal, segTree[p * 2 + 1].maxVal);
}
// 查询区间最小值或最大值
int query(int p, int ql, int qr, int opt) {
if (ql <= segTree[p].l && segTree[p].r <= qr) {
return opt == 1 ? segTree[p].minVal : segTree[p].maxVal;
}
int mid = (segTree[p].l + segTree[p].r) / 2;
int res;
if (ql <= mid && qr > mid) {
int leftRes = query(p * 2, ql, qr, opt);
int rightRes = query(p * 2 + 1, ql, qr, opt);
res = opt == 1 ? min(leftRes, rightRes) : max(leftRes, rightRes);
} else if (ql <= mid) {
res = query(p * 2, ql, qr, opt);
} else {
res = query(p * 2 + 1, ql, qr, opt);
}
return res;
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
}
build(1, 1, n);
while (m--) {
int opt, l, r;
scanf("%d%d%d", &opt, &l, &r);
int res = query(1, l, r, opt);
printf("%d\n", res);
}
return 0;
}
```
这个程序的时间复杂度为 $O(m \log n)$,其中 $m$ 表示询问次数,$n$ 表示数据规模。