Description
水果姐今天心情不错，来到了水果街。
水果街有n家水果店，呈直线结构，编号为1~n，每家店能买水果也能卖水果，并且同一家店卖与买的价格一样。
学过oi的水果姐迅速发现了一个赚钱的方法：在某家水果店买一个水果，再到另外一家店卖出去，赚差价。
就在水果姐窃喜的时候，cgh突然出现，他为了为难水果姐，给出m个问题，每个问题要求水果姐从第x家店出发到第y家店，途中只能选一家店买一个水果，然后选一家店（可以是同一家店，但不能往回走）卖出去，求每个问题中最多可以赚多少钱。
Input
第一行n，表示有n家店
下来n个正整数，表示每家店一个苹果的价格。
下来一个整数m，表示下来有m个询问。
下来有m行，每行两个整数x和y，表示从第x家店出发到第y家店。
Output
有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
Hint
0<=苹果的价格<=10^8
1<=n,m<=200000
思路
- 线段树记录：最大值，最小值，从左往右的答案，从右往左的答案(两个买卖水果点在两个不同区间/相同区间，有点像旅馆Hotel（USACO 2008 February Gold）)
- 有可能从右往左走，所以answer=max{右区间的最大值-左区间的最小值/左区间的最大值-右区间的最小值，左区间的答案，右区间的答案}
代码
#include <iostream>
#include <cstdio>
#define maxn 200005
using namespace std;
int n,m,v[maxn];
struct fdfdfd{int l,r,maxx,minn,ans1,ans2;}a[maxn<<2];
void pushup(int x)
{
a[x].maxx=max(a[x<<1].maxx,a[x<<1|1].maxx);
a[x].minn=min(a[x<<1].minn,a[x<<1|1].minn);
a[x].ans1=max(a[x<<1|1].maxx-a[x<<1].minn,max(a[x<<1].ans1,a[x<<1|1].ans1));
a[x].ans2=max(a[x<<1].maxx-a[x<<1|1].minn,max(a[x<<1].ans2,a[x<<1|1].ans2));
}
void build(int x,int left,int right)
{
a[x].l=left; a[x].r=right;
if(left==right){a[x].maxx=a[x].minn=v[left]; return;}
int mid=(left+right)>>1;
build(x<<1,left,mid); build(x<<1|1,mid+1,right);
pushup(x);
}
fdfdfd query(int x,int left,int right)
{
if(a[x].l>right||a[x].r<left) return (fdfdfd){0,0,-1,0x7fffffff,-1,-1};
if(left<=a[x].l&&right>=a[x].r) return a[x];
fdfdfd temp1=query(x<<1,left,right),temp2=query(x<<1|1,left,right),temp;
temp.ans1=max(max(temp1.ans1,temp2.ans1),temp2.maxx-temp1.minn);
temp.ans2=max(max(temp1.ans2,temp2.ans2),temp1.maxx-temp2.minn);
temp.minn=min(temp1.minn,temp2.minn);
temp.maxx=max(temp1.maxx,temp2.maxx);
return temp;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&v[i]);
build(1,1,n); scanf("%d",&m);
while(m--)
{
int f1,f2; scanf("%d%d",&f1,&f2);
if(f1==f2) puts("0");
else if(f1<f2) printf("%d
",query(1,f1,f2).ans1);
else printf("%d
",query(1,f2,f1).ans2);
}
return 0;
}