[Gym102268J] Jealous Split

神仙题,之前听人提过。但是凸性完全不会证,会了之后补上 QwQ。

做法

显然使 \(\sum s_i^2\) 取到最小值的划分一定满足条件。

所以二分斜率求出 \(\sum s_i^2\) 最小的序列就行了。

代码

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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;

typedef long double ld;

const int maxn = 200010;

struct line {
__int128 k, b;
int c;
line (__int128 k_=0, __int128 b_=0, int c_=0) {
k = k_, b = b_, c = c_;
}
__int128 cal(__int128 x) {
return k * x + b;
}
} Q[maxn];

ld cross(const line &l1, const line &l2) {
return (l1.b - l2.b) / (l2.k - l1.k);
}

int n, k;
__int128 a[maxn], dp[maxn], S[maxn];
int mn_cnt[maxn], mx_cnt[maxn];

int cmp_less(int x, int y) {
return x < y;
}

int cmp_greater(int x, int y) {
return x > y;
}

void caldp(__int128 cur, int* cnt, int (*cmp) (int, int)) {
int s = 0, t = 0;
Q[t++] = line(0, cur, 0);
for (int i = 1; i <= n; i++) {
while (s + 1 < t) {
__int128 v1 = Q[s].cal(S[i]), v2 = Q[s+1].cal(S[i]);
if (v1 > v2 || (v1 == v2 && cmp(Q[s+1].c, Q[s].c))) {
++ s;
} else break;
}
dp[i] = Q[s].cal(S[i]) + S[i] * S[i];
cnt[i] = Q[s].c + 1;
line l(- 2 * S[i], dp[i] + S[i] * S[i] + cur, cnt[i]);
if (s < t && Q[t-1].k == l.k) {
if (l.b == Q[t-1].b) {
if (!cmp(l.c, Q[t-1].c)) {
l = Q[t-1];
}
} else {
if (l.b > Q[t-1].b) {
l = Q[t-1];
}
}
-- t;
}
while (s < t-1 && (Q[t-1].b - Q[t-2].b) * (Q[t-2].k - l.k) >= (l.b - Q[t-2].b) * (Q[t-2].k - Q[t-1].k)) {
-- t;
}
Q[t++] = l;
}
}

int main() {
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++) {
int x;
scanf("%d", &x);
a[i] = x;
}
for (int i = 1; i <= n; i++) {
S[i] = S[i-1] + a[i];
}
__int128 L = 0, R = 3e19;
while (1) {
__int128 mid = (L + R) / 2;
caldp(mid, mn_cnt, cmp_less);
caldp(mid, mx_cnt, cmp_greater);
if (mn_cnt[n] <= k && mx_cnt[n] >= k) {
break;
} else if (mn_cnt[n] > k) {
L = mid + 1;
} else R = mid - 1;
}
__int128 mid = (L + R) / 2;
vector<int> ans;
int cur = n;
while (cur) {
for (int l = cur; l >= 1; l--) {
if (mn_cnt[l-1] <= k-1 && mx_cnt[l-1] >= k-1 && (dp[l-1] + (S[cur] - S[l-1]) * (S[cur] - S[l-1]) + mid == dp[cur])) {
cur = l-1;
ans.push_back(cur);
-- k;
break;
}
}
}
puts("Yes");
ans.pop_back(); reverse(ans.begin(), ans.end());
for (int i = 0; i < ans.size(); i++) {
printf("%d ", ans[i]);
}
puts("");
return 0;
}