单调栈 牛客网 区区区间间间

发表于 更新于 分类于 阅读次数：

用单调栈算出以每个数作为区间最小数和最大数的区间的范围，算出每个数字的贡献。

区区区间间间

题目链接

思路

以前做过一道CF的类似的， 不过这两道题还是不太一样，为了不需要N^2复杂度，我们用单调栈预处理出每个数字的作为区间最小数和最大数的贡献，然后O（N）遍历即可。把我卡住的是如果有相等数字的情况，我们必须保证两个相等的数字它们扩展的范围并不一样，否则贡献就重叠了， 也就是代码中的加不加等于号的问题。

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
83
84
85
86
87
88
89
90
#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;
}