题意：
在给出的区间内求出最大买进卖出的差价。
思路：
对于弱数据：维护一个从左到右的最大差价和最小值。即当发现当前值比最小值小的时候更新最小值，否则看一下当前值与之前最小值的差价是否比最大差价大，是就更新最大差价。时间复杂度是O(m*n)
对于强数据：利用线段树维护一个最大差价、最大值和最小值，查询的时候求出询问的范围内左右子树的最大差价，然后再利用RMQ求出[l, mid]的最小值和[mid+1, r]的最大值，然后返回max(df[rt<<1], df[rt<<1|1], RMQ(mid+1, r)-RMQ(l, mid));这个的时间复杂度是O(nlgn)+m*O(nlgn)
Tips：
我的做法是维护了最大值和最小值以便求出最大差值，也可以不维护这个，直接利用RMQ求出最大值和最小值，然后求最大差值。
Code：
#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std; const int MAXN = ;
int mx[MAXN<<], mn[MAXN<<], df[MAXN<<];
int dpx[MAXN][], dpn[MAXN][];
int val[MAXN]; void makermq(int n)
{
for (int j = ; (<<j) <= n; ++j)
for (int i = ; i+(<<j)- <= n; ++i) {
dpn[i][j] = min(dpn[i][j-], dpn[i+(<<(j-))][j-]);
dpx[i][j] = max(dpx[i][j-], dpx[i+(<<(j-))][j-]);
}
} int rmqx(int s, int v)
{
int k = (int)(log((v-s+)*1.0)/log(2.0));
return max(dpx[s][k], dpx[v-(<<k)+][k]);
} int rmqn(int s, int v)
{
int k = (int)(log((v-s+)*1.0)/log(2.0));
return min(dpn[s][k], dpn[v-(<<k)+][k]);
} void PushUp(int rt)
{
mx[rt] = max(mx[rt<<], mx[rt<<|]);
mn[rt] = min(mn[rt<<], mn[rt<<|]);
df[rt] = max(df[rt<<], df[rt<<|]);
df[rt] = max(df[rt], mx[rt<<|]-mn[rt<<]);
} void Build(int rt, int l, int r)
{
if (l == r) {
scanf("%d", &mx[rt]);
mn[rt] = mx[rt];
dpn[l][] = dpx[l][] = mx[rt];
return;
}
int mid = (l+r)/;
Build(rt<<, l, mid);
Build(rt<<|, mid+, r);
PushUp(rt);
} int query(int l, int r, int L, int R, int rt)
{
if (L >= l && R <= r) {
return df[rt];
}
int mid = (L+R)/;
int ans = ;
if (r <= mid) ans = query(l, r, L, mid, rt<<);
else if (l > mid) ans = query(l, r, mid+, R, rt<<|);
else {
ans = query(l, r, L, mid, rt<<);
ans = max(ans, query(l, r, mid+, R, rt<<|)); ans = max(ans, rmqx(mid+, r)-rmqn(l, mid));
}
return ans;
} int main()
{
//freopen("in.txt", "r", stdin);
int n;
int q, a, b;
while (~scanf("%d", &n)) {
n++;
memset(df, , sizeof(df));
memset(mx, , sizeof(mx));
memset(mn, , sizeof(mn));
Build(, , n);
makermq(n); scanf("%d", &q);
while (q--) {
scanf("%d %d", &a, &b);
a++, b++;
printf("%d\n", query(a, b, , n, ));
}
puts("");
}
return ;
}
链接：http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1832
外传野史：这道题其实是某学长的面试题，当时那个学长太紧张了，没想清楚，只想到了可以用线段树维护最大值和最小值来解，但是面试官貌似也不认识线段树，然后提示说这个是股票，最小值必须在最大值的左面，这样单纯的维护最大值最小值就不好使了。
所以正解的确是用线段树，但是是用线段树维护差值，并用RMQ来帮忙维护 差值 = 右子树指定范围内最大值-左子树指定范围内最小值 的问题。
这个是zz想到的啦，给他一个good~