【代码源每日一题Div1】子串的最大差「单调栈？」「ST表 + 二分」

子串的最大差

题目描述：

给你n个数字，求所有子区间的最大数减最小数的和

思路：

我们考虑单独计算对于每个数字i能产生的贡献，即计算哪些子区间[l, r]满足l<=i<=r，且a[i]作为区间最大值或者作为区间最小值时的贡献

显然，最大值和最小值可以分开计算

对于a[i]我们找左边第一个大于a[i]的位置+1，计作l，找i右边第一个大于a[i]的位置-1，计作r

则a[i]作为最大值时的贡献应该是+ a[i]*(i-l+1)*(r-i+1)

但是由于存在相同的元素，所以就会重复计算某些区间的答案

比如：5 5 5 5，对于每个5都会找到l=1,r=4，这样会重复计算答案

为了避免这个情况，我们找r的时候可以找第一个大于等于a[i]的位置-1作为r，这样对于a[i]找到的区间，最后一个等于a[i]的位置一定是i

对于最小值的计算方法也一样

那如何快速地求位置l或者r呢，我们可以用st表+二分答案的方法来实现

过了以后才发现这个题正解是单调栈

#include 
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 500000 + 50
int n, m, k, x;
ll a, b;
int tr[MAX];

int lg[MAX];
int minx[MAX][22];
int maxn[MAX][22];
void init(){
    for(int i = 2; i <= n; ++i){
        lg[i] = lg[i / 2] + 1;
    }
    for(int i = 1; i <= n; ++i)minx[i][0] = maxn[i][0] = tr[i];
    for(int j = 1; j <= lg[n]; ++j){
        for(int i = 1; i + (1<<j) - 1 <= n; ++i){
            maxn[i][j] = max(maxn[i][j-1], maxn[i + (1<<(j-1))][j-1]);
            minx[i][j] = min(minx[i][j-1], minx[i + (1<<(j-1))][j-1]);
        }
    }
}
int cal_max(int l, int r){
    int d = lg[r-l+1];
    return max(maxn[l][d], maxn[r-(1<<d)+1][d]);
}
int cal_min(int l, int r){
    int d = lg[r-l+1];
    return min(minx[l][d], minx[r-(1<<d)+1][d]);
}

void work(){
    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> tr[i];
    }
    init();
    ll ans = 0;
    for(int i = 1; i <= n; ++i){
        int l = 1, r = i;
        while(l <= r){
            int mid = (l + r) / 2;
            if(cal_max(mid, i) == tr[i])r = mid - 1;
            else l = mid + 1;
        }
        a = l;
        l = i; r = n;
        while(l <= r){
            int mid = (l + r) / 2;
            if(cal_max(i, mid) == tr[i])l = mid + 1;
            else r = mid - 1;
        }
        b = l - 1;
        ans += (b - a + 1) * tr[i];
        
        l = 1; r = i;
        while(l <= r){
            int mid = (l + r) / 2;
            if(cal_min(mid, i) == tr[i])r = mid - 1;
            else l = mid + 1;
        }
        a = l;
        
        l = i; r = n;
        while(l <= r){
            int mid = (l + r) / 2;
            if(cal_min(i, mid) == tr[i])l = mid + 1;
            else r = mid - 1;
        }
        b = l - 1;
        ans -= (b - a + 1) * tr[i];
    }
    cout << ans << endl;
}


int main(){
    io;
    work();
    return 0;
}

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
91
92
93