codeforces #333 div 2 D. Lipshitz Sequence

Note: This article is available in Chinese only. 本文暂无英文版本。 View original

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 contradiction
We’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}

Related