专业 网站设计公司价格,3d建模培训学校,品牌网站建设 意义,wordpress扩展class名称买水果
Description
水果姐今天心情不错#xff0c;来到了水果街。
水果街有n家水果店#xff0c;呈直线结构#xff0c;编号为1~n#xff0c;每家店能买水果也能卖水果#xff0c;并且同一家店卖与买的价格一样。
学过oi的水果姐迅速发现了一个赚钱的方法#xff1a…买水果
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;
}
