血战二级市场 视频题解可点击此处查看 题目阅读 AC狗迷上了炒股，想要在二级市场赚钱。 市场中有一种概念叫做波幅，代表一段时间内股票的最高价和最低价的差额。 AC狗现在已经拿到了狗星农工科技公司连续N天的收盘价，他自己计算出了这N天的波幅，现在他想知道这N天出了空集之外所有连续子序列的波幅之和。 题意抽象 一个长度为n的序列Ai，求这个序列当中所有子序列（包括自身）当中，所有差值的和。 算法分析 面对求区间最大值问题，我们可以使用单调栈来解决这道题目。 在这道题目中，我们对于区间可以假设状态为f(i)或者f(i,j),进行转移。 设f(i)表示以i作为左端点的所有区间的最大值减最小值。 之后开始考虑状态转移: 假设f(i-1)进行转移，那么Ai便会更新一些区间的最大值或者最小值。 我们可以维护两个单调队列，一个上升，一个下降，符合Ai更新的特性。每次都算出更新的最大值和最小值的差进行累加即为答案。 代码讲解

#include<bits/stdc++.h> using namespace std; typedef long long ll ; const int N = 5e5+5; const int INF = 1e9; ll n,a[N],dp[N]; ll anser ; ll s1[N],s2[N],w1[N],w2[N]; int t1,t2; int main(){ cin >> n ; for(int i = 1 ; i <= n ; i ++ ){ cin >> a[i]; dp[i] = dp[i-1]; ll sum = 0 ; ll k = 0 ; while(a[s1[t1]] < a[i] && t1){ k += w1[t1]; sum += (a[i] - a[s1[t1]]) * w1[t1] ; t1 -- ; } s1[t1] = i ; w1[t1] = 1 + k ; dp[i] += sum ; sum = 0 ; k = 0 ; while(a[s2[t2]] > a[i] && t2){ k += w2[t2]; sum += (a[s2[t2]]-a[i]) * w2[t2]; t2-- ; } s2[ t2] = i; w2[t2] = 1 + k; dp[i] += sum; anser += dp[i]; } cout << anser << endl; return 0; } [链接描述]( url