题解 本题是一道明显的区间查询问题，可以很快想到线段树之类的数据结构。（不知为什么分到了区间dp里，预处理至少，dp真的能过吗？）
首先是建树。由题意，显然每个结点都应包括区间左端点、右端点、最大值、最小值，由于要走单向的路线，所以还应该有区间从左到右走的最大差值和从右到左走的最大差值。其中max和min的值很容易维护，那么剩下的就是两个最大差值了。
先考虑叶子结点，那这两个方向的最大差值显然都是0； 线段树的核心是合并两个区间，那已知两个子区间，如何把最大差值和并呢？ 以从左到右走的最大差值为例，这要分三种情况： 1、差值在左子树的区间取得，而左子树的所有情况都是知道的； 2、差值在右子树的区间取得，而右子树的所有情况都是知道的； 3、差值为右子树的最大值减去左子树的最大值，而左子树和右子树的所有情况都是知道的； 这三种情况取最大即可。 从右到左走的最大差值同理，只需要把第3种情况改成左子树的最大值减去右子树的最小值即可。
树建好了，，那本题也就基本解决了。 对于 x==y 的情况，答案一定是0，直接输出吧，省时间。 对于这一段查询区间，从根开始找，若线段树结点对应的区间被查询区间所包含，直接返回答案；若不涉及右子树，则只查询左子树；若不涉及左子树，则只查询右子树：这是线段树的基本查询方式了。 左右子树同时涉及时，只需要在左子树和右子树中分别查询最大差值和最值，答案就是最大差值的最大值和最值差之间的最大值。
Code
#include <cstdio>#include <algorithm>#define tlc(k) (k << 1)#define trc(k) (k << 1 | 1)using namespace std;const int maxn = 800100, root = 1, nil = 0;int tmax[maxn], tmin[maxn], ansl[maxn], ansr[maxn], lc[maxn], rc[maxn];int n, m, a[maxn >> 2];void update(int k){tmax[k] = max(tmax[tlc(k)], tmax[trc(k)]);tmin[k] = min(tmin[tlc(k)], tmin[trc(k)]);ansl[k] = max(ansl[tlc(k)], ansl[trc(k)]);ansl[k] = max(ansl[k], tmax[trc(k)] – tmin[tlc(k)]);ansr[k] = max(ansr[tlc(k)], ansr[trc(k)]);ansr[k] = max(ansr[k], tmax[tlc(k)] – tmin[trc(k)]);}void build(int rot, int l, int r){if(l == r){tmax[rot] = tmin[rot] = a[l];ansl[rot] = ansr[rot] = 0;lc[rot] = rc[rot] = l;return;}int mid = ((l + r) >> 1);lc[rot] = l; rc[rot] = r;build(tlc(rot), l, mid);build(trc(rot), mid + 1, r);update(rot);}int querymax(int rot, int l, int r){if(l <= lc[rot] && r >= rc[rot]) return tmax[rot];int mid = ((lc[rot] + rc[rot]) >> 1);if(r <= mid) return querymax(tlc(rot), l, r);else if(l > mid) return querymax(trc(rot), l, r);(querymax(tlc(rot), l, r), querymax(trc(rot), l, r));}int querymin(int rot, int l, int r){if(l <= lc[rot] && r >= rc[rot]) return tmin[rot];int mid = ((lc[rot] + rc[rot]) >> 1);if(r <= mid) return querymin(tlc(rot), l, r);else if(l > mid) return querymin(trc(rot), l, r);(querymin(tlc(rot), l, r), querymin(trc(rot), l, r));}int queryl(int rot, int l, int r){if(l <= lc[rot] && r >= rc[rot]) return ansl[rot];int mid = ((lc[rot] + rc[rot]) >> 1);if(r <= mid) return queryl(tlc(rot), l, r);else if(l > mid) return queryl(trc(rot), l, r);else{int tmp = max(queryl(tlc(rot), l, mid), queryl(trc(rot), mid + 1, r));tmp = max(tmp, querymax(trc(rot), mid + 1, r) – querymin(tlc(rot), l, mid));return tmp;} }int queryr(int rot, int l, int r){if(l <= lc[rot] && r >= rc[rot]) return ansr[rot];int mid = ((lc[rot] + rc[rot]) >> 1);if(r <= mid) return queryr(tlc(rot), l, r);else if(l > mid) return queryr(trc(rot), l, r);else{int tmp = max(queryr(tlc(rot), l, mid), queryr(trc(rot), mid + 1, r));tmp = max(tmp, querymax(tlc(rot), l, mid) – querymin(trc(rot), mid + 1, r));return tmp;} }void init(){scanf(“%d”, &n);for(int i = 1; i <= n; ++i) scanf(“%d”, &a[i]);build(root, 1, n);scanf(“%d”, &m);}void work(){int x, y;while(m–){scanf(“%d%d”, &x, &y);if(x < y) printf(“%d\n”, queryl(root, x, y));else if(x > y) printf(“%d\n”, queryr(root, y, x));else puts(“0”);}}int main(){init();work();return 0;}
去陌生的街角，去做一切我们曾经或现在也很想做的事情，
