买水果
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;
}