线段树保姆级教程

买水果

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;
}