【题解】HackerRank-Pair Sum

题目

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;
}