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
| #include<iostream> #include<algorithm> #include<cstring> #include<cstdio> #include<stack> using namespace std; #define pii pair<int,int> #define mp make_pair #define int long long #define MAXN 200006 #define MAXV 1000006 int n , mx; int h[MAXN] , stk[MAXN] , top = 0; int L[MAXN] , R[MAXN];
int T[MAXV << 2]; int que( int rt , int l , int r , int L , int R ) { if( L <= l && R >= r ) return T[rt]; int m = l + r >> 1 , ret = -0x3f3f3f3f; if( L <= m ) ret = max( ret , que( rt << 1 , l , m , L , R ) ); if( R > m ) ret = max( ret , que( rt << 1 | 1 , m + 1 , r , L , R ) ); return ret; } void mdfy( int rt , int l , int r , int p , int c ) { T[rt] = max( T[rt] , c ); if( l == r ) return; int m = l + r >> 1; if( p <= m ) mdfy( rt << 1 , l , m , p , c ); else mdfy( rt << 1 | 1 , m + 1 , r , p , c ); } int S[MAXN] , len[MAXN]; namespace solve2 { int l[MAXN] , r[MAXN] , d[MAXN] , rt , stk[MAXN] , tp = 0; bool cmp( int x , int y ) { return h[x] < h[y]; } void build(){ for( int i = 1 ; i <= n ; ++ i ) { int k=tp; while (k > 0 && h[stk[k-1]] > h[i]) --k; if (k) r[stk[k-1]]=i; if (k<tp) l[i]=stk[k]; stk[k++]=i; tp=k; } } int res(0); void dfs( int u , int ll , int rr ) { if( l[u] ) if( h[u] == ll ) dfs( l[u] , ll , ll ); else res += u - l[u] , dfs( l[u] , ll , h[l[u]] ); if( r[u] ) if( h[u] == rr ) dfs( r[u] , rr , rr ); else res += r[u] - u , dfs( r[u] , h[r[u]] , rr ); } int main() { build(); dfs( stk[0] , -1 , -1 ); return res; } } int tt; signed main() { cin >> n; for( int i = 1 ; i <= n ; ++ i ) scanf("%lld",&h[i]) , mx = max( mx , h[i] ) , S[i] = S[i - 1] + h[i]; cin >> tt; for( int i = 0 ; i <= mx * 4 + 3 ; ++ i ) T[i] = -0x3f3f3f3f; for( int i = 1 ; i <= n ; ++ i ) { int t = que( 1 , 1 , mx , 1 , h[i] ); L[i] = t; mdfy( 1 , 1 , mx , h[i] , i ); } int ans = 0; for( int i = 1 ; i <= n ; ++ i ) if( L[i] != -0x3f3f3f3f ) len[i] = len[L[i]] + ( h[i] - h[L[i]] ) * L[i] + S[i - 1] - S[L[i]] - ( i - 1 - L[i] ) * h[i] , ans += len[i] , ans += i * ( n - i ); else len[i] = S[i] - h[i] * i , ans += len[i] , ans += i * ( n - i ); cout << ans << ' '; if( tt == 1 ) return 0; cout << solve2::main() << endl; }
|