买水果
Description
水果姐今天心情不错，来到了水果街。
水果街有n家水果店，呈直线结构，编号为1~n，每家店能买水果也能卖水果，并且同一家店卖与买的价格一样。
学过oi的水果姐迅速发现了一个赚钱的方法：在某家水果店买一个水果，再到另外一家店卖出去，赚差价。
就在水果姐窃喜的时候，cgh突然出现，他为了为难水果姐，给出m个问题，每个问题要求水果姐从第x家店出发到第y家店，途中只能选一家店买一个水果，然后选一家店（可以是同一家店，但不能往回走）卖出去，求每个问题中最多可以赚多少钱。
Input
第一行n，表示有n家店
下来n个正整数，表示每家店一个苹果的价格。
下来一个整数m，表示下来有m个询问。
下来有m行，每行两个整数x和y，表示从第x家店出发到第y家店。
Output
有m行。
每行对应一个询问，一个整数，表示面对cgh的每次询问，水果姐最多可以赚到多少钱。
挺简单。
首先要维护一个最大mx和最小mn
然后维护一个_aa_和_bb_，分别表示从l~r或r~l的最大。
每次只需要去查询_aa_和_bb_(不需要修改）
pushup如下：
void pushup(int u) {
tr[u].mx = max(tr[u << 1].mx,tr[u << 1 | 1].mx);
tr[u].mn = min(tr[u << 1].mn,tr[u << 1 | 1].mn);
tr[u]._aa_ = max({tr[u << 1 | 1].mx - tr[u << 1].mn,tr[u << 1]._aa_,tr[u << 1 | 1]._aa_});
tr[u]._bb_ = max({tr[u << 1].mx - tr[u << 1 | 1].mn,tr[u << 1]._bb_,tr[u << 1 | 1]._bb_});
}好做完了
#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
int w[N];
struct owl {
int l, r,mx,mn,_aa_,_bb_;
} tr[N * 4];
void pushup(int u) {
tr[u].mx = max(tr[u << 1].mx,tr[u << 1 | 1].mx);
tr[u].mn = min(tr[u << 1].mn,tr[u << 1 | 1].mn);
tr[u]._aa_ = max({tr[u << 1 | 1].mx - tr[u << 1].mn,tr[u << 1]._aa_,tr[u << 1 | 1]._aa_});
tr[u]._bb_ = max({tr[u << 1].mx - tr[u << 1 | 1].mn,tr[u << 1]._bb_,tr[u << 1 | 1]._bb_});
}
void build(int u, int l, int r) {
tr[u].l = l;
tr[u].r = r;
if (l == r) {
tr[u].mx = tr[u].mn = w[l];
return ;
}
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
int querymn(int u, int l, int r) {
if (tr[u].l >= l && tr[u].r <= r) {
return tr[u].mn;
} else {
int mid = tr[u].l + tr[u].r >> 1;
int v = 2e9;
if (l <= mid) {
v = min(v, querymn(u << 1, l, r));
}
if (r > mid) {
v = min(v, querymn(u << 1 | 1, l, r));
}
return v;
}
}
int querymx(int u, int l, int r) {
if (tr[u].l >= l && tr[u].r <= r) {
return tr[u].mx;
} else {
int mid = tr[u].l + tr[u].r >> 1;
int v = -2e9;
if (l <= mid) {
v = max(v, querymx(u << 1, l, r));
}
if (r > mid) {
v = max(v, querymx(u << 1 | 1, l, r));
}
return v;
}
}
int query_aa_(int u, int l, int r) {
if (tr[u].l >= l && tr[u].r <= r) {
return tr[u]._aa_;
} else {
int mid = tr[u].l + tr[u].r >> 1;
int v = -2e9;
if (l <= mid && mid < r){
v = max(v,querymx(u << 1 | 1,mid + 1,r) - querymn(u << 1,l,mid));
}
if (l <= mid) {
v = max(v, query_aa_(u << 1, l, r));
}
if (r > mid) {
v = max(v, query_aa_(u << 1 | 1, l, r));
}
return v;
}
}
int query_bb_(int u, int l, int r) {
if (tr[u].l >= l && tr[u].r <= r) {
return tr[u]._bb_;
} else {
int mid = tr[u].l + tr[u].r >> 1;
int v = -2e9;
if (l <= mid && mid < r){
v = max(v,querymx(u << 1,l,mid) - querymn(u << 1 | 1,mid + 1,r));
}
if (l <= mid) {
v = max(v, query_bb_(u << 1, l, r));
}
if (r > mid) {
v = max(v, query_bb_(u << 1 | 1, l, r));
}
return v;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n, m;
cin >> n;
for (int i = 1; i <= n; i ++ ) {
cin >> w[i];
}
cin >> m;
build(1, 1, n);
while (m -- ) {
int l,r;
cin >> l >> r;
if (l < r){
cout << query_aa_(1,l,r) << endl;
}
else{
cout << query_bb_(1,r,l) << endl;
}
}
return 0;
}