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代表能到达的右边和左边的最远位置。
/* ***********************************************
Author :111qqz
Created Time :2015年12月22日 星期二 22时58分35秒
File Name :code/cf/#333/D.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair
21#define left lllllxy
22#define right rrrrrxy
23using namespace std;
24const double eps = 1E-8;
25const int dx4[4]={1,0,0,-1};
26const int dy4[4]={0,-1,1,0};
27const int inf = 0x3f3f3f3f;
28const int N=1E5+7;
29int n ;
30int q;
31LL a[N],b[N];
32int left[N];
33int right[N];
34int main()
35{
36 #ifndef ONLINE_JUDGE
37 freopen("code/in.txt","r",stdin);
38 #endif
1 cin>>n;
2 cin>>q;
3 for ( int i = 1 ; i <= n ; i++)
4 {
5 cin>>a[i];
1 }
2 for ( int i = 2 ;i <= n ; i++)
3 {
4 b[i] = abs(a[i]-a[i-1]);
5 }
1 while (q--)
2 {
3 int l,r;
4 scanf("%d %d",&l,&r);
5 l++;
1 for ( int i = l ; i <= r ; i++) //以b[i]为最大值，最左能到达多远。
2 {
3 left[i] = i ;
4 while (left[i]>l&&b[i]>b[left[i]-1])
5 left[i] = left[left[i]-1];
6 }
7 for ( int i = r ; i >= l ; i--) //最右能到达多远。
8 {
9 right[i] = i;
10 while (right[i] < r &&b[i]>=b[right[i]+1])
11 right[i] = right[right[i] + 1];
12 }
13 LL ans= 0 ;
14 for ( int i = l ; i <= r ; i++)
15 ans +=(LL)(right[i]-i+1)*(LL)(i-left[i]+1)*b[i];
16 cout<<ans<<endl;
}
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}