include<bits/stdc++.h>

using namespace std;
const int mxn = 1e6 + 1;
int a[mxn], t1[4 * mxn], t2[4 * mxn];
void build(int id, int l, int r){
if (l == r){
t1[id] = a[l];
t2[id] = a[l];
} else {
int mid = (l + r) / 2;
build(id * 2, l, mid);
build(id * 2 + 1, mid + 1, r);
t1[id] = max(t1[id * 2], t1[id * 2 + 1]);
t2[id] = min(t2[id * 2], t2[id * 2 + 1]);
}
}
int query1(int id, int l, int r, int u, int v){
if (v < l || r < u){
return -1e18;
} else if (u <= l && r <= v){
return t1[id];
} else {
int mid = (l + r) / 2;
return max(query1(id * 2, l, mid, u, v), query1(id * 2 + 1, mid + 1, r, u, v));
}
}
int query2(int id, int l, int r, int u, int v){
if (v < l || r < u){
return 1e18;
} else if (u <= l && r <= v){
return t2[id];
} else {
int mid = (l + r) / 2;
return min(query2(id * 2, l, mid, u, v), query2(id * 2 + 1, mid + 1, r, u, v));
}
}
void sub1(){
int n;
long long ans = 0;
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
build(1, 1, n);
for (int i = 1; i < n; ++i)
for (int j = i + 1; j <= n; ++j)
ans += abs(query1(1, 1, n, i, j) - query2(1, 1, n, i, j));
cout << ans;
}
void sub2(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
long long n;
long long ans = 0, l;
cin >> n;
for (int i = 0; i < n; ++i) cin >> a[i];
stack<int> mx, mn;
for (long long i = 0; i <= n; ++i){
while (!mx.empty() && (i == n || a[mx.top()] < a[i])){
long long id = mx.top();
mx.pop();
if (mx.empty())
l = -1;
else
l = mx.top();
ans += a[id] * (i - id) * (id - l);
}
mx.push(i);
while (!mn.empty() && (i == n || a[mn.top()] > a[i])){
long long id = mn.top();
mn.pop();
if (mn.empty())
l = -1;
else
l = mn.top();
ans -= a[id] * (i - id) * (id - l);
}
mn.push(i);
}
cout << ans;
}
int main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//freopen("1356.inp", "r", stdin);
//freopen("1356.out", "w", stdout);
sub2();
return 0;
}

coder ngu

Hi, I love coding although I code very bad 😊

tôi mới học lập trình xin hãy chỉ bảo tôi nhiều hơn

hihihi