题目大意:
给出长度为n的数组和q个询问,每次问(x,y)区间内最大值和最小值的差是多少
思路:
1.适合用树状数组做此区间求值,首先要明白普通的树状数组的tree[x]表示区间(x-(x&-x),x]的区间和,现在改为求最值,则tree[x]表示为区间(x-(x&-x),x]的最值,建树部分稍作改变即可,询问部分用query函数实现
2.每次询问区间时有两种可能,若x<=y-(y&-y),此时返回max(tree[y],query(x,y-(y&-y)),否则返回max(h[y],query(x,y-1)) (h[y]表示y处对应的数值)
代码如下:
#include<bits/stdc++.h>
#include<algorithm>
#include<unordered_set>
#include<unordered_map>
typedef long long ll;
using namespace std;
#define N 50005
#define lowbit(x) (x&(-x))
int a[N],b[N],h[N]; int n, m;
//初始化
void init() {
memset(a, 0, sizeof(a));
for (int i = 1; i <= n; i++)b[i] = 1000005;
}
//最大
void add(int x, int k) {
for(int i=x;i<=n;i+=lowbit(i)) a[i] = max(a[i],k);
}
//最小
void addmin(int x, int k) {
for (int i = x; i <= n; i += lowbit(i)) b[i] = min(b[i], k);
}
//区间最大值
int query(int x,int y) {
if(x==y)return h[x];
//把区间做拆分
if (y - lowbit(y) >= x)return max(a[y], query(x, y - lowbit(y)));
else return max(h[y], query(x, y - 1));
}
//区间最小值
int querymin(int x, int y) {
if (x == y)return h[x];
if (y - lowbit(y) >= x)return min(b[y], querymin(x, y - lowbit(y)));
else return min(h[y], querymin(x, y - 1));
}
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
init();
for (int i = 1; i <= n; i++) {
cin >> h[i];
//建树
add(i,h[i]); addmin(i,h[i]);
}
while (m--) {
int x, y; cin >> x >> y;
cout << query(x,y)-querymin(x,y) << "\n";
}
return 0;
}