http://codeforces.com/contest/602/problem/D
题意:见题目描述。
思路:我们很容易发现,l[h]函数其实就是在求区间斜率的最大值。哦不对,是斜率的绝对值的最大值。而且一个显而易见的结论是,斜率最大值一定是由相邻的点得到。画图可以很容易看出。
具体的证明见这里:
In order to prove it properly, we’ll consider three numbers Ai, Aj, Ak (i < j < k) and show that one of the numbers L1(i, j),L1(j, k) is ≥ L1(i, k). W.l.o.g., we may assume Ai ≤ Ak. There are 3 cases depending on the position of Aj relative to Ai, Ak:
- Aj > Ai, Ak — we can see that L1(i, j) > L1(i, k), since |Aj - Ai| = Aj - Ai > Ak - Ai = |Ak - Ai| and j - i < k - i; we just need to divide those inequalities
- Aj < Ai, Ak — this is similar to the previous case, we can prove that L1(j, k) > L1(i, k) in the same way
- Ai ≤ Aj ≤ Ak — this case requires more work:
- we’ll denote d1y = Aj - Ai, d2y = Ak - Aj, d1x = j - i, d2x = k - j
- then, L1(i, j) = d1y / d1x, L1(j, k) = d2y / d2x, L1(i, k) = (d1y + d2y) / (d1x + d2x)
- let’s prove it by contradiction: assume that L1(i, j), L1(j, k) < L1(i, k)
- d1y + d2y = L1(i, j)d1x + L1(j, k)d2x < L1(i, k)d1x + L1(i, k)d2x = L1(i, k)(d1x + d2x) = d1y + d2y, which is a contradiction
We’ve just proved that to any L1 computed for two elements A[i], A[k] with k > i + 1, we can replace one of i, j by a point jbetween them without decreasing L1; a sufficient amount of such operations will give us k = i + 1. Therefore, the max. L1can 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,也就是说一共有4*4个区间的最大值为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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 |
/* *********************************************** Author :111qqz Created Time :2015年12月22日 星期二 22时58分35秒 File Name :code/cf/#333/D.cpp ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <cmath> #include <cstdlib> #include <ctime> #define fst first #define sec second #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define ms(a,x) memset(a,x,sizeof(a)) typedef long long LL; #define pi pair < int ,int > #define MP make_pair #define left lllllxy #define right rrrrrxy using namespace std; const double eps = 1E-8; const int dx4[4]={1,0,0,-1}; const int dy4[4]={0,-1,1,0}; const int inf = 0x3f3f3f3f; const int N=1E5+7; int n ; int q; LL a[N],b[N]; int left[N]; int right[N]; int main() { #ifndef ONLINE_JUDGE freopen("code/in.txt","r",stdin); #endif cin>>n; cin>>q; for ( int i = 1 ; i <= n ; i++) { cin>>a[i]; } for ( int i = 2 ;i <= n ; i++) { b[i] = abs(a[i]-a[i-1]); } while (q--) { int l,r; scanf("%d %d",&l,&r); l++; for ( int i = l ; i <= r ; i++) //以b[i]为最大值,最左能到达多远。 { left[i] = i ; while (left[i]>l&&b[i]>b[left[i]-1]) left[i] = left[left[i]-1]; } for ( int i = r ; i >= l ; i--) //最右能到达多远。 { right[i] = i; while (right[i] < r &&b[i]>=b[right[i]+1]) right[i] = right[right[i] + 1]; } LL ans= 0 ; for ( int i = l ; i <= r ; i++) ans +=(LL)(right[i]-i+1)*(LL)(i-left[i]+1)*b[i]; cout<<ans<<endl; } #ifndef ONLINE_JUDGE fclose(stdin); #endif return 0; } |
说点什么
您将是第一位评论人!