codeforces #333 div 2 D. Lipshitz Sequence
http://codeforces.com/contest/602/problem/D 题意：见题目描述。 思路：我们很容易发现，l[h]函数其实就是在求区间斜率的最大值。哦不对，是斜率的绝对值的最大值。而且一个显而易见的结论是，斜率最大值一定是由相邻的点得到。画图可以很容易看出。
具体的证明见这里：In order to prove it properly, we’ll consider three numbers A__i, A__j, A__k (i < j < k) and show that one of the numbers _L_1(i, j),_L_1(j, k) is ≥ _L_1(i, k). W.l.o.g., we may assume A__i ≤ A__k. There are 3 cases depending on the position of A__j relative to A__i, A__k:
* _A__j_ > _A__i_, _A__k_ — we can see that _L_1(_i_, _j_) > _L_1(_i_, _k_), since |_A__j_ - _A__i_| = _A__j_ - _A__i_ > _A__k_ - _A__i_ = |_A__k_ - _A__i_| and _j_ - _i_ < _k_ - _i_; we just need to divide those inequalities * _A__j_ < _A__i_, _A__k_ — this is similar to the previous case, we can prove that _L_1(_j_, _k_) > _L_1(_i_, _k_) in the same way * _A__i_ ≤ _A__j_ ≤ _A__k_ — this case requires more work: * we'll denote _d_1_y_ = _A__j_ - _A__i_, _d_2_y_ = _A__k_ - _A__j_, _d_1_x_ = _j_ - _i_, _d_2_x_ = _k_ - _j_ * then, _L_1(_i_, _j_) = _d_1_y_ / _d_1_x_, _L_1(_j_, _k_) = _d_2_y_ / _d_2_x_, _L_1(_i_, _k_) = (_d_1_y_ + _d_2_y_) / (_d_1_x_ + _d_2_x_) * let's prove it by contradiction: assume that _L_1(_i_, _j_), _L_1(_j_, _k_) < _L_1(_i_, _k_) * _d_1_y_ + _d_2_y_ = _L_1(_i_, _j_)_d_1_x_ + _L_1(_j_, _k_)_d_2_x_ < _L_1(_i_, _k_)_d_1_x_ + _L_1(_i_, _k_)_d_2_x_ = _L_1(_i_, _k_)(_d_1_x_ + _d_2_x_) = _d_1_y_ + _d_2_y_, which is a contradictionWe’ve just proved that to any _L_1 computed for two elements A[i], A[k] with k > i + 1, we can replace one of i, j by a point _j_between them without decreasing _L_1; a sufficient amount of such operations will give us k = i + 1. Therefore, the max. _L_1can be found by only considering differences between adjacent points.
这样子就好做了很多。由于斜率绝对值的最大值一定在由相邻的两个点得到。而相邻两个点的横坐标差1，所以斜率的绝对值就变成了相邻元素差的最大值。因此我们可以预处理一个数组b，表示相邻元素的差的绝对值。
接下来的问题就变成了如何求b的一段区间里的所有子区间的最大值的和。我们的思路是考虑这个区间里每个元素对答案的贡献。显然，对于b中越大的元素，它对答案的贡献会越多，因为会有更多包含它的区间以它为最大值。具体来讲，对于这个区间的每一个元素，我们可以分别向左和右边扩展，看最大能到哪里。
比如3 4 3 8 2 7 1，对于8，左边可以到达3，与8的距离为3，右边可以到达1，与8的距离为3，那么8对答案的贡献为(3+1)*(3+1)8，也就是说一共有44个区间的最大值为8.对于7，左边可以到2，距离7为1，右边可以到1，距离7长度为1，那么7对答案的贡献就是（1+1）×（1+1）*7，也就是有4个区间的最大值为7.分别为{2}，{2,7}，{7,1}，{2,7,1}
由于q不算很大，可以直接搞…用两个数组right和left代表能到达的右边和左边的最远位置。
1/* ***********************************************
2Author :111qqz
3Created Time :2015年12月22日 星期二 22时58分35秒
4File Name :code/cf/#333/D.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27#define left lllllxy
28#define right rrrrrxy
29using namespace std;
30const double eps = 1E-8;
31const int dx4[4]={1,0,0,-1};
32const int dy4[4]={0,-1,1,0};
33const int inf = 0x3f3f3f3f;
34const int N=1E5+7;
35int n ;
36int q;
37LL a[N],b[N];
38int left[N];
39int right[N];
40int main()
41{
42 #ifndef ONLINE_JUDGE
43 freopen("code/in.txt","r",stdin);
44 #endif
45
46 cin>>n;
47 cin>>q;
48 for ( int i = 1 ; i <= n ; i++)
49 {
50 cin>>a[i];
51
52 }
53 for ( int i = 2 ;i <= n ; i++)
54 {
55 b[i] = abs(a[i]-a[i-1]);
56 }
57
58 while (q--)
59 {
60 int l,r;
61 scanf("%d %d",&l,&r);
62 l++;
63
64 for ( int i = l ; i <= r ; i++) //以b[i]为最大值，最左能到达多远。
65 {
66 left[i] = i ;
67 while (left[i]>l&&b[i]>b[left[i]-1])
68 left[i] = left[left[i]-1];
69 }
70 for ( int i = r ; i >= l ; i--) //最右能到达多远。
71 {
72 right[i] = i;
73 while (right[i] < r &&b[i]>=b[right[i]+1])
74 right[i] = right[right[i] + 1];
75 }
76 LL ans= 0 ;
77 for ( int i = l ; i <= r ; i++)
78 ans +=(LL)(right[i]-i+1)*(LL)(i-left[i]+1)*b[i];
79 cout<<ans<<endl;
80
81 }
82
83 #ifndef ONLINE_JUDGE
84 fclose(stdin);
85 #endif
86 return 0;
87}