【题解】HackerRank-Pair Sum

Posted on In Disqus:

题目

https://www.hackerrank.com/challenges/pair-sums/problem

题意

给定一个数列，对于所有区间，求区间内两两之积之和的最大值。

题解

设 \(s_k=\sum_{i=1}^{k} a_i,ss_k=\sum_{i=1}^k a_i^2\)，\(f_i\) 为以第 \(i\) 个元素结尾的最大值的 2 倍。 \[ f_i=\max\{(s_i-s_j)^2-(ss_i-ss_j)\} \\ f_i=(s_i^2-ss_i)-2s_is_j+ss_j + s_j^2\\ x=-2s_j,y=ss_j+s_j^2,k=s_i \\ f_i=C_i+kx+y \] \(k\) 不单调，\(x\) 不单调，维护上凸壳。

代码

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
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#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 = 5E5 + 100;
LL a[maxn], s[maxn], ss[maxn];

struct P {
    LL x, y;
};
P operator - (P& a, P& b) { return {a.x - b.x, a.y - b.y}; }
__int128 det(P a, P b) {
    return (__int128)a.x * b.y - (__int128)a.y * b.x;
}
P p[maxn], q[maxn];
LL pp[maxn], qq[maxn];
LL ans = -1e18;

void go(int l, int r) {
    if (l + 1 == r) { p[l] = {-2 * s[l], ss[l] + s[l] * s[l]}; pp[l] = l; return; }
    int m = l + r >> 1;
    go(l, m);
    go(m, r);
    static deque<P> x; x.clear();
    FOR (i, l, m) {
        int t;
        while ((t = x.size()) >= 2 && det(x[t - 1] - x[t - 2], p[i] - x[t - 1]) >= 0)
            x.pop_back();
        x.push_back(p[i]);
    }
    FOR (i, m, r) {
        LL k = pp[i];
        auto get = [&](P& p){ return s[k] * p.x + p.y; };
        while (x.size() >= 2 && get(x[0]) <= get(x[1])) x.pop_front();
        ans = max(ans, get(x[0]) + (s[k] * s[k] - ss[k]));
    }

    merge(p + l, p + m, p + m, p + r, q + l, [](const P& a, const P& b)->bool {
        return a.x < b.x;
    });
    copy(q + l, q + r, p + l);
    merge(pp + l, pp + m, pp + m, pp + r, qq + l, [](const int& a, const int& b){
        return -s[a] > -s[b];
    });
    copy(qq + l, qq + r, pp + l);
}

int main() {
#ifdef zerol
    freopen("in", "r", stdin);
#endif
    int n; cin >> n;
    FOR (i, 1, n + 1) scanf("%lld", &a[i]);
    FOR (i, 1, n + 1) {
        s[i] = s[i - 1] + a[i];
        ss[i] = ss[i - 1] + a[i] * a[i];
    }
    go(0, n + 1);
    cout << ans / 2 << endl;
}