时间限制: 2 s
空间限制: 256000 KB
题目描述 Description
水果姐今天心情不错，来到了水果街。
水果街有n家水果店，呈直线结构，编号为1~n，每家店能买水果也能卖水果，并且同一家店卖与买的价格一样。
学过oi的水果姐迅速发现了一个赚钱的方法：在某家水果店买一个水果，再到另外一家店卖出去，赚差价。
就在水果姐窃喜的时候，cgh突然出现，他为了为难水果姐，给出m个问题，每个问题要求水果姐从第x家店出发到第y家店，途中只能选一家店买一个水果，然后选一家店（可以是同一家店，但不能往回走）卖出去，求每个问题中最多可以赚多少钱。
输入描述 Input Description
第一行n，表示有n家店
下来n个正整数，表示每家店一个苹果的价格。
下来一个整数m，表示下来有m个询问。
下来有m行，每行两个整数x和y，表示从第x家店出发到第y家店。
输出描述 Output Description
有m行。
每行对应一个询问，一个整数，表示面对cgh的每次询问，水果姐最多可以赚到多少钱。
样例输入 Sample Input
10
2 8 15 1 10 5 19 19 3 5
4
6 6
2 8
2 2
6 3
样例输出 Sample Output
0
18
0
14
数据范围及提示 Data Size & Hint
0<=苹果的价格<=10^8
0<n,m<=200000
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=200010; struct node { int maxx,minx,l_rsum,r_lsum; int l,r; }e[N<<2]; inline int mx(int a,int b,int c) { int q=a>b?a:b; return q>c?q:c; } void pushup(node &ro,node &ll,node &rr) { ro.maxx=max(ll.maxx,rr.maxx); ro.minx=min(ll.minx,rr.minx); ro.l_rsum=mx(ll.l_rsum,rr.l_rsum,rr.maxx-ll.minx); ro.r_lsum=mx(ll.r_lsum,rr.r_lsum,ll.maxx-rr.minx); } void build(int ro,int l,int r) { e[ro].l=l,e[ro].r=r; if(l==r) { int x; scanf("%d",&x); e[ro].maxx=x,e[ro].minx=x; return; } int mid=(l+r)>>1; build(ro<<1,l,mid); build(ro<<1|1,mid+1,r); pushup(e[ro],e[ro<<1],e[ro<<1|1]); return; } node query(int ro,int l,int r) { if(l<=e[ro].l&&e[ro].r<=r) return e[ro]; int mid=(e[ro].l+e[ro].r)>>1; node answer,lson,rson; if(r<=mid) return query(ro<<1,l,r); else if(l>mid) return query(ro<<1|1,l,r); lson=query(ro<<1,l,mid); rson=query(ro<<1|1,mid+1,r); pushup(answer,lson,rson); return answer; } int main() { int n; scanf("%d",&n); build(1,1,n); //for(int i=1;i<=20;i++) printf("%d %d %d %d %d %d ",e[i].maxx,e[i].minx,e[i].l_rsum,e[i].r_lsum,e[i].l,e[i].r); int m; scanf("%d",&m); for(int i=1;i<=m;i++) { int a,b; scanf("%d %d",&a,&b); if(a<=b) { node ans=query(1,a,b); printf("%d ",ans.l_rsum); } else { node ans=query(1,b,a); printf("%d ",ans.r_lsum); } } return 0; }
谢谢Brian551帮助；
可以去看看他的文章：http://blog.csdn.net/brian551/article/details/77688615