[USACO07JAN] Balanced Lineup G(树状数组)

题目大意:

给出长度为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;
}