c++测试样例由多组测试数据组成。每个样例包含两行:第一行输入两个正整数 n 和 m; 第二行输入 n 个整数 ai。接下来 m 行,每行输入 2 个整数li, ri 1 <= n, m <= 105, 1 <= li <= ri <= n,-109 <= ai <= 109 输出 每个样例输出 m 行,每行包含一个整数,表示 [l, r] 区间的最大值。
时间: 2024-02-03 15:04:35 浏览: 44
以下是一个可能的 C++ 实现,使用线段树来维护区间最大值:
```c++
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
const int MAXN = 1e5 + 5;
int n, m;
int a[MAXN];
struct Node {
int l, r, maxn;
};
Node tree[MAXN * 4];
void build(int i, int l, int r) {
tree[i].l = l;
tree[i].r = r;
if (l == r) {
tree[i].maxn = a[l];
return;
}
int mid = (l + r) / 2;
build(i * 2, l, mid);
build(i * 2 + 1, mid + 1, r);
tree[i].maxn = max(tree[i * 2].maxn, tree[i * 2 + 1].maxn);
}
int query(int i, int l, int r) {
if (tree[i].l >= l && tree[i].r <= r) {
return tree[i].maxn;
}
int res = INT_MIN;
int mid = (tree[i].l + tree[i].r) / 2;
if (l <= mid) {
res = max(res, query(i * 2, l, r));
}
if (r > mid) {
res = max(res, query(i * 2 + 1, l, r));
}
return res;
}
int main() {
while (cin >> n >> m) {
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
build(1, 1, n);
for (int i = 0; i < m; i++) {
int l, r;
cin >> l >> r;
cout << query(1, l, r) << endl;
}
}
return 0;
}
```
假设输入有 T 组测试样例,时间复杂度为 O(T(n + m)logn),其中 n 和 m 分别为数组长度和查询次数。