题目描述
输入一串数字,给你 M 个询问,每次询问就给你两个数字 X,Y,要求你说出 X 到 Y 这段区间内的最大数。
输入格式
第一行两个整数 N,M 表示数字的个数和要询问的次数;
接下来一行为 N 个数;
接下来 M 行,每行都有两个整数 X,Y。
输出格式
输出共 M 行,每行输出一个数。
数据范围
1≤N≤105,
1≤M≤106,
1≤X≤Y≤N,
数列中的数字均不超过231−1
输入样例:
10 2
3 2 4 5 6 8 1 2 9 7
1 4
3 8
输出样例:
5
8
C ++ 代码
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 100010, INF = 1e9;
int n, m;
int w[N];
//线段树结点,l,r 分别表示区间的左右端点, maxv表示该区间的最大值
struct Node{
int l, r;
int maxv;
}tr[4 * N];
//函数更新结点信息,即求最大值
void pushup(int u){
tr[u].maxv = max(tr[u << 1].maxv, tr[u << 1 | 1].maxv);
}
//函数建立线段树,即建树
void build(int u, int l, int r){//l, r 表示当前结点区间, u表示当前结点的实际存储位置
if(l == r ) tr[u] = {l, r, w[l]};//若达到叶结点
else{
tr[u] = {l, r};
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);//左右递归
pushup(u);//更新信息
}
}
//区间查询,即在区间l, r中找最大值
int query(int u, int l, int r){//l, r 表示当前查询区间,u表示当前结点编号
if(tr[u].r < l || tr[u].l > r) return 0;//查询区间与当前结点区间无交集
if(tr[u].l >= l && tr[u].r <= r) return tr[u].maxv;//返回查询区间的最大值
int mid = tr[u].l + tr[u].r >> 1;
int maxv = -INF;
if(l <= mid) maxv = query(u << 1, l, r);//左子区间与l, r有重叠,递归
if(r > mid) maxv =max(maxv,query(u << 1 | 1, l, r));//右子区间与l, r 有重叠,递归
return maxv;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
//使用cin超时
// cin >> n >> m;
// for(int i = 1; i <= n; i ++) cin >> w[i];//读取数据
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i ++) scanf("%d", &w[i]);//读取数据
build(1, 1, n);//在区间l——n建树
int l, r;
while(m --){
// cin >> l >> r;
// cout << query(1, l, r) << endl;//在区间l,r之间寻找最大值
scanf("%d%d",&l, &r);
printf("%d\n",query(1,l,r));
}
return 0;
}
您好,query函数中,if (l <= mid) maxv = query(u << 1, l, r); 虽然所求区间是 [l, r] 但是左边的部分只能 取到 [l,mid] ? 同样的下面的 [l,r] 不应该是 [mid+1,r] 吗?
我觉得 是– 就 左边来看的话:如果r<mid的 话 那就有可能多取了,同理,右边 如果l<mid+1 也可能多取