【题解】HackerRank - The Strange Function

Posted on In Disqus:

题目

https://www.hackerrank.com/contests/hourrank-25/challenges/the-strange-function

题意

对于给定的一列数，对于所有区间，求 f(l, r) 的最大值。

f(l, r) = (区间 gcd 绝对值) * (区间和 - 区间最大值)

题解

  • 如果固定右端点，扩展左端点，那么 gcd 的值最多变化 \(logC\) 次（C 为数列中最大的可能值），而且从左到右 gcd 值是单调递增的。
  • 如果右端新加入一个点，那个将原来的每一段的 gcd 都对于新的数取 gcd，再进行去重就能得到新的 gcd 的分段信息。
  • 对于每一段，需要求区间和和区间最大值之差的最大值。用线段树维护这个量。
  • 区间和很好处理，对于区间最大值使用了一个栈来维护每一个数的作为最大值的作用区间，当有新的值加入可能导致一些原先的最大值失效，因此要进行撤销操作。
  • 复杂度 \(O(n\log C+n\log 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 <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(args...) do { cout << "\033[32;1m" << #args<< " -> "; err(args); } while (0)
#else
#define dbg(...)
#endif
void err() { cout << "\033[39;0m" << endl; }
template<typename T, typename... Args>
void err(T a, Args... args) { cout << a << ' '; err(args...); }
// -----------------------------------------------------------------------------
const int maxn = 5E4 + 100;
const LL INF = 1E18;
struct IntervalTree {
#define lson o * 2, l, (l + r) >> 1
#define rson o * 2 + 1, ((l + r) >> 1) + 1, r
    static const int M = maxn << 2;
    LL maxv[M], addv[M];
    void maintain(int o, int l, int r) {
        if (l < r) {
            int lc = o * 2, rc = o * 2 + 1;
            maxv[o] = max(maxv[lc], maxv[rc]);
        } else maxv[o] = 0;
        maxv[o] += addv[o];
    }
    void update(int ql, int qr, int o, int l, int r, LL v) {
        if (ql > r || l > qr) return;
        if (ql <= l && r <= qr) addv[o] += v;
        else {
            update(ql, qr, lson, v); update(ql, qr, rson, v);
        }
        maintain(o, l, r);
    }
    LL query(int ql, int qr, int o, int l, int r, LL add = 0) {
        if (ql > r || l > qr) return -INF;
        if (ql <= l && r <= qr) return maxv[o] + add;
        add += addv[o];
        return max(query(ql, qr, lson, add), query(ql, qr, rson, add));
    }
} R;

LL a[maxn];
struct P {
    int l, r;
    LL v;
};

vector<P> gcd;
stack<P> Max;

int main() {
#ifdef zerol
    freopen("in", "r", stdin);
#endif
    int n;
    cin >> n;
    FOR (i, 1, n + 1) scanf("%lld", &a[i]);
    LL ans = -INF;
    FOR (i, 1, n + 1) {
        for (P& p: gcd)
            p.v = __gcd(p.v, abs(a[i]));
        gcd.push_back({i, i, abs(a[i])});
        vector<P> nxt_gcd;
        for (P& p: gcd)
            if (nxt_gcd.empty() || nxt_gcd.back().v != p.v)
                nxt_gcd.push_back(p);
            else nxt_gcd.back().r = p.r;
        gcd.swap(nxt_gcd);

        while (!Max.empty() && a[i] >= Max.top().v) {
            P& p = Max.top();
            R.update(p.l, p.r, 1, 1, n, p.v);
            Max.pop();
        }
        Max.push({Max.empty() ? 1 : Max.top().r + 1, i, a[i]});
        P& cur = Max.top();
        R.update(cur.l, cur.r, 1, 1, n, -cur.v);
        R.update(1, i, 1, 1, n, a[i]);

//        FOR (j, 1, i + 1)
//            printf("%d%c", R.query(j, j, 1, 1, n), j == _j - 1 ? '\n' : ' ');

        for (P& p: gcd)
            ans = max(ans, p.v * R.query(p.l, p.r, 1, 1, n));
    }
    cout << ans << endl;
}