NamomoCampDaily1

时间：2023-04-25

NamomoCamp Daily 1

codeforces原题网址https://codeforces.com/contest/817/problem/D

代码源oj网址http://oj.daimayuan.top/problem/436

题解：

对于每一个数，我们考虑这个数在所有区间的总贡献。

当以这个数为最小值时，计算出向左可以延伸的长度，以及向右延伸的长度，从而计算以其为最小值的总区间个数。

同理，当以这个数为最大值时，计算两边可延伸的长度，从而计算总区间个数。

这一步可以利用单调栈来实现。

在一个数 a i a_i ai为最小值的所有区间，那么 a n s ans ans便要减去 a i ∗ m i n _ s u m i a_i*min_sum_i ai∗min_sumi，即在这些区间里面， a i a_i ai都处于减数的位置。

而在 a i a_i ai为最大值的所有区间， a n s ans ans便要加上 a i ∗ m a x _ s u m i a_i*max_sum_i ai∗max_sumi，即每个 a i a_i ai都处于被减数的位置。

注意

要注意反着做单调栈时，相同元素是否需要留在栈内。

代码

// Good Good Study, Day Day AC.#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define ffor(i,a,b) for(int i=(a) ;i<=(b) ;i++)#define rrep(i,a,b) for(int i=(a) ;i>=(b) ;i--)#define mst(v,s) memset(v,s,sizeof(v))#define IOS ios::sync_with_stdio(false),cin.tie(0)#define ll long long#define INF 0x7f7f7f7f7f7f7f7f#define inf 0x7f7f7f7f#define PII pair#define int long longusing namespace std;const int N = 5e5 + 10;int n, T;int a[N];void ready(){IOS;cin >> n;ffor(i, 1, n) cin >> a[i];}int rmax[N], rmin[N], lmax[N], lmin[N];stack s;int ans;inline void clear_() {while (s.size()) {s.pop();}}void work(){clear_();ffor(i, 1, n) {while (s.size() && a[i] <= a[s.top()]) s.pop();if (!s.size()) lmin[i] = 1;else lmin[i] = s.top() + 1;s.push(i);}clear_();rrep(i, n, 1) {while (s.size() && a[i] < a[s.top()]) s.pop();if (!s.size()) rmin[i] = n;else rmin[i] = s.top() - 1;s.push(i);}clear_();ffor(i, 1, n) {while (s.size() && a[i] >= a[s.top()]) s.pop();if (!s.size()) lmax[i] = 1;else lmax[i] = s.top() + 1;s.push(i);}clear_();rrep(i, n, 1) {while (s.size() && a[i] > a[s.top()]) s.pop();if (!s.size()) rmax[i] = n;else rmax[i] = s.top() - 1;s.push(i);}ffor(i, 1, n) {ans -= a[i] * ((i - lmin[i] + 1) * (rmin[i] - i + 1));ans += a[i] * ((i - lmax[i] + 1) * (rmax[i] - i + 1));}cout << ans;}signed main(){ready();work();return 0;}

上一篇：从尾到头打印链表

下一篇：pandas库学习总结1