单调栈 牛客网 区区区间间间 发表于 2019-11-05 | 分类于 ACM题解 | 阅读次数: 用单调栈算出以每个数作为区间最小数和最大数的区间的范围,算出每个数字的贡献。## 区区区间间间题目链接### 思路以前做过一道CF的类似的, 不过这两道题还是不太一样,为了不需要N^2复杂度,我们用单调栈预处理出每个数字的作为区间最小数和最大数的贡献,然后O(N)遍历即可。把我卡住的是如果有相等数字的情况,我们必须保证两个相等的数字它们扩展的范围并不一样,否则贡献就重叠了, 也就是代码中的加不加等于号的问题。123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990#include <cstdio>#include <cstdlib>#include <cstring>#include <string>#include <cmath>#include <algorithm>#include <iostream>#include <queue>#include <stack>#include <map>#include <set>#include <bitset>typedef long long ll;using namespace std;const int mod = 1e9+7;const int inf = 0x3f3f3f3f;ll a[100005];ll l[100005], r[100005];int main(){ int T, n; cin >> T; while(T--) { stack<int>S1,S2; scanf("%d",&n); ll Maxsum = 0,Minsum = 0 ; for(int i = 1; i <= n; ++i) { scanf("%lld",&a[i]); } for(int i = 1; i <= n; ++i) { while(!S1.empty() && a[i] <= a[S1.top()] ) { S1.pop(); } if(S1.empty()) l[i] = 1; else l[i] = S1.top() + 1; S1.push(i); } for(int i = n; i >= 1; --i) { while(!S2.empty() && a[i] < a[S2.top()]) { S2.pop(); } if(S2.empty()) r[i] = n; else r[i] = S2.top() - 1; S2.push(i); } for(int i = 1; i <= n; ++i) { Minsum -= ((r[i] - i + 1) * (i - l[i]) + r[i] - i) * a[i]; } stack<int>S3,S4; for(int i = 1; i <= n; ++i) { while(!S3.empty() && a[i] >= a[S3.top()]) { S3.pop(); } if(S3.empty()) l[i] = 1; else l[i] = S3.top() + 1; S3.push(i); } for(int i = n; i >= 1;--i) { while(!S4.empty() && a[i] > a[S4.top()]) { S4.pop(); } if(S4.empty()) r[i] = n; else r[i] = S4.top() - 1; S4.push(i); } for(int i = 1; i <= n; ++i) { Maxsum += ((r[i] - i + 1) * (i - l[i]) + r[i] - i) * a[i]; } cout << Maxsum + Minsum << '\n'; } return 0;} 打赏