题目链接：传送门

Description

给你一个序列，定义一个区间的价值是，这个区间里的最大值乘以最小值。求出所有区间长度对应的最大价值。数据为全随机

Solution

由于数据是随机的，我们可以用分治法来解决这道题 我们用Solve(l, r)来求出区间[l,r]中各种区间长度的最大价值。然后，我们找出[l,r]中的最小值。固定了最小值以后，我们再去枚举最大值，算出各个价值。我们能发现，随着区间变长，如果最小值是固定的，那么最大值只有可能越来越大，价值也会越来越大。所以我们要把区间短的答案给区间长的更新。然后分治搞就行了

Code

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
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int Maxn = 1e5 + 100;

int A[Maxn], Ans[Maxn], N;
int tmp[Maxn];

inline void Solve (int l, int r)
{
    if (l > r) return ;
    int pos = 0;
    for (int i = l; i <= r; ++i)
        if (!pos || A[i] < A[pos]) pos = i;
    int len = r - l + 1;
    for (int i = 1; i <= len; ++i) tmp[i] = 0;
    for (int i = l; i <= pos; ++i)
        tmp[pos - i + 1] = max(tmp[pos - i + 1], A[i] * A[pos]);
    for (int i = pos; i <= r; ++i)
        tmp[i - pos + 1] = max(tmp[i - pos + 1], A[i] * A[pos]);
    int lastans = 0;
    for (int i = 1; i <= len; ++i)
    {
        lastans = max(lastans, tmp[i]);
        Ans[i] = max(Ans[i], lastans);
    }
    Solve(l, pos - 1);
    Solve(pos + 1, r);
}

main()
{
#ifdef hk_cnyali
    freopen("A.in", "r", stdin);
    freopen("A.out", "w", stdout);
#endif
    while (scanf("%lld", &N) != EOF)
    {
        memset(Ans, 0, sizeof (Ans));
        for (int i = 1; i <= N; ++i)
            scanf("%lld", &A[i]);
        Solve (1, N);
        for (int i = 1; i <= N; ++i)
            printf("%lld\n", Ans[i]);
    }
    return 0;
}