[Codeforces] D. Imbalanced Array

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : D. Imbalanced Array
Source            : Codeforces
Category          : Divide & Conquer
Algorithm         : Divide & Conquer
Verdict           : Accepted

1. #include "bits/stdc++.h"  
2. #include "ext/pb_ds/assoc_container.hpp"  
3. #include "ext/pb_ds/tree_policy.hpp"  
4. #include "ext/rope"  
5.   
6. using namespace std;  
7. using namespace __gnu_pbds;  
8. using namespace __gnu_cxx;  
9.   
10. #define FI              freopen("in.txt", "r", stdin)  
11. #define FO              freopen("out.txt", "w", stdout)  
12. #define FAST            ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)  
13.   
14. #define FOR(i, n)       for (int i = 1; i <= n; i++)  
15. #define For(i, n)       for (int i = 0; i < n; i++)  
16. #define ROF(i, n)       for (int i = n; i >= 1; i--)  
17. #define Rof(i, n)       for (int i = n-1; i >= 0; i--)  
18. #define FORI(i, n)      for (auto i : n)  
19. #define FORAB(i, a, b)  for (int i = a; i <= b; i++)  
20.   
21. #define ll              long long  
22. #define ull             unsigned long long  
23. #define vi              vector <int>  
24. #define vl              vector <ll>  
25. #define pii             pair <int, int>  
26. #define pll             pair <ll, ll>  
27. #define mk              make_pair  
28. #define ff              first  
29. #define ss              second  
30. #define eb              emplace_back  
31. #define em              emplace  
32. #define pb              push_back  
33. #define ppb             pop_back  
34. #define All(a)          a.begin(), a.end()  
35. #define memo(a, b)      memset(a, b, sizeof a)  
36. #define Sort(a)         sort(All(a))  
37. #define ED(a)           Sort(a), a.erase(unique(All(a)), a.end())  
38. #define rev(a)          reverse(All(a))  
39. #define sz(a)           (int)a.size()  
40. #define max3(a, b, c)   max(a, max(b, c))  
41. #define min3(a, b, c)   min(a, min(b, c))  
42. #define maxAll(a)       *max_element(All(a))  
43. #define minAll(a)       *min_element(All(a))  
44. #define allUpper(a)     transform(All(a), a.begin(), :: toupper)  
45. #define allLower(a)     transform(All(a), a.begin(), :: tolower)  
46. #define endl            '\n'  
47. #define nl              puts("")  
48. #define ub              upper_bound  
49. #define lb              lower_bound  
50. #define Exp             exp(1.0)  
51. #define PIE             2*acos(0.0)  
52. #define Sin(a)          sin(((a)*PIE)/180.0)  
53. #define EPS             1e-9  
54.   
55. template <typename T> using orderset = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;  
56.   
57. // rope <int> Rope;  
58.   
59. // int dr[] = {1, -1, 0, 0}; // 4 Direction  
60. // int dc[] = {0, 0, 1, -1};  
61. // int dr[] = {0, 0, 1, -1, 1, 1, -1, -1}; // 8 Direction  
62. // int dc[] = {1, -1, 0, 0, 1, -1, 1, -1};  
63. // int dr[] = {-1, 1, -2, -2, -1, 1, 2, 2}; // knight Moves  
64. // int dc[] = {-2, -2, -1, 1, 2, 2, 1, -1};  
65.   
66. #define here                                cerr << "Here" << endl;  
67. #define trace1(x)                           cerr << #x << ": " << x << endl;  
68. #define trace2(x, y)                        cerr << #x << ": " << x << " | " << #y << ": " << y << endl;  
69. #define trace3(x, y, z)                     cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;  
70. #define trace4(a, b, c, d)                  cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;  
71. #define trace5(a, b, c, d, e)               cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;  
72. #define trace6(a, b, c, d, e, f)            cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;  
73.   
74. inline int setbit(int mask, int pos)        { return mask |= (1 << pos); }  
75. inline int resetbit(int mask, int pos)      { return mask &= ~(1 << pos); }  
76. inline int togglebit(int mask, int pos)     { return mask ^= (1 << pos); }  
77. inline bool checkbit(int mask, int pos)     { return (bool)(mask & (1 << pos)); }  
78.   
79. #define ones(mask)                          __builtin_popcount(mask)   // count set bit  
80. #define onesLL(mask)                        __builtin_popcountll(mask) // for long long  
81. #define lzeros(mask)                        __builtin_clz(mask)        // no of leading zeros  
82. #define tzeros(mask)                        __builtin_ctz(mask)        // no of trailing zeros  
83.   
84. inline int read()                           { int a; scanf("%d", &a); return a; }  
85. inline ll readLL()                          { ll a; scanf("%lld", &a); return a; }  
86. inline double readDD()                      { double a; scanf("%lf", &a); return a; }  
87.   
88. template <typename T> string toString(T num) { stringstream ss; ss << num; return ss.str(); }  
89. int toInt(string s)                          { int num; istringstream iss(s); iss >> num; return num;  }  
90. ll toLLong(string s)                         { ll num; istringstream iss(s); iss >> num; return num; }  
91.   
92. //#define inf             1e8  
93. #define mod             1000000007  
94.   
95. static const int maxn = 1e6 + 5;  
96. static const int logn = 18;  
97. static const int inf  = 1e9 + 5;  
98.   
99. int n;  
100. int arr[maxn], max_at[maxn], min_at[maxn];  
101.   
102. ll max_sum(int s, int e)  
103. {  
104.       if (s == e) return arr[s];  
105.       int mid = (s + e) / 2;  
106.       // In this function we calculate sum of maximum of all sub-arrays which  
107.       // have 'mid' index present.  
108.       // Example: arr[] = {1, 2, mid, 6, 5}  
109.       // Then sum of maximum for these sub-arrays are -  
110.       // {1, 2, mid, 6}, {1, 2, mid, 6, 5}, {2, mid, 6}, {2, mid, 6, 5}, {mid, 6}, {mid, 6, 5}  
111.       int cur_max = 0;  
112.       ll sum = 0;  
113.       for (int i = mid+1; i <= e; i++)  
114.       {  
115.             cur_max = max(cur_max, arr[i]);  
116.             sum += cur_max;  
117.             max_at[i] = cur_max;  
118.       }  
119.       cur_max = 0;  
120.       int right_idx = mid+1;  
121.       ll ans = 0;  
122.       for (int i = mid; i >= s; i--)  
123.       {  
124.             cur_max = max(cur_max, arr[i]);  
125.             // Finding the maximum index after mid such that value at that index is  
126.             // greater than current max.  
127.             while (right_idx <= e && max_at[right_idx] <= cur_max)  
128.             {  
129.                   sum -= max_at[right_idx];  
130.                   // This maximum is subtracted from sum and right_idx is incremented.  
131.                   // This means that for arrays ending at this index cur_max is maximum value.  
132.                   right_idx++;  
133.             }  
134.             // Calculate number of arrays where current max is maximum.  
135.             ll num = right_idx - mid - 1;  
136.             // The sum of maximum of the arrays ending at indices >= right_idx is  
137.             // stored in variable sum.  
138.             ans += sum + num * cur_max;  
139.       }  
140.       return ans + max_sum(s, mid) + max_sum(mid+1, e);  
141. }  
142.   
143. ll min_sum(int s, int e)  
144. {  
145.       if (s == e) return arr[s];  
146.       int mid = (s + e) >> 1;  
147.       int cur_min = inf;  
148.       ll sum = 0;  
149.       for (int i = mid+1; i <= e; i++)  
150.       {  
151.             cur_min = min(cur_min, arr[i]);  
152.             sum += cur_min;  
153.             min_at[i] = cur_min;  
154.       }  
155.       cur_min = inf;  
156.       int right_idx = mid+1;  
157.       ll ans = 0;  
158.       for (int i = mid; i >= s; i--)  
159.       {  
160.             cur_min = min(cur_min, arr[i]);  
161.             while (right_idx <= e && min_at[right_idx] > cur_min)  
162.             {  
163.                   sum -= min_at[right_idx];  
164.                   right_idx++;  
165.             }  
166.             ll num = right_idx - mid - 1;  
167.             ans += sum + num * cur_min;  
168.       }  
169.       return ans + min_sum(s, mid) + min_sum(mid+1, e);  
170. }  
171.   
172. int main()  
173. {  
174.       n = read();  
175.       for (int i = 1; i <= n; i++) arr[i] = read();  
176.       printf("%lld", max_sum(1, n) - min_sum(1, n));  
177. }