5.31 训练 A 世上最幸福的女孩

懒得卡空间了!

我们考虑对于一段区间来说,在全局加 $x$ 后,长度为 $l$ 的段的最优答案是啥。不难发现是 $lx + b$ ,其中 $b$ 为长度为 $l$ 段的和的最大值。因此我们可以对每个 $l = 1\sim n$ ,求出一条直线,然后对这个直线求一个凸包就可以做询问在全局加 $x$ 的情况下的和了。

然后考虑区间询问怎么办。首先我们可以把区间询问拆成 $O(\log n)$ 个线段树节点。然后对每个节点,我们维护出最大的后缀和,最大的前缀和,最大的区间本身子段,以及区间的和。之需要对这 $O(\log n)$ 个节点做 $dp[u] = pre_u + S_{u-1} + \max_{v < u}(suf_v - S_v)$ 这个东西即可,这个玩意是 $O(\log n)$ 的。所以我们之需要对一个线段树区间维护这几个东西即可。

不难发现最大后缀和和最大前缀和都可以维护一个关于 $x$ 的凸包。然后在 pushup 求出最大子段和的时候,我们要做的其实就是把 左右儿子的后缀凸包和前缀凸包加起来 再和 左右儿子的最大子段和凸包 chkmax 后的结果 再 chkmax 一次即可。看起来凸包的大小会膨胀,但是事实上由于本质不同斜率只有 $O(len)$ 个,所以实际上每个位置的凸包大小也是 $O(len)$ 的。而这几个过程都可以归并来做,因此复杂度是 $O(n\log n)$ 的。

考虑询问的过程,看起来我们需要在每个凸包上二分一下 $x$ ,事实上离线询问后,我们可以按照 $x$ 排序处理询问。这样就之需要移动一个指针即可,复杂度 $O(n\log n + m\log n)$ 。看起来足以通过本题。但是事实上这玩意有一个 $O(n\log n)$ 的空间,即使压紧开在构造数据也需要 300MB 左右,炸掉了 128MB ,因此需要一些优秀的卡空间技巧来通过此题。具体来说,需要在对每层建立凸包后丢弃掉下面一层,然后把询问挂在节点上之类的操作。最后可以卡到严格 $O(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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 300006
#pragma pack(1)
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int, int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin(), (x).end()
#define mem(a) memset(a, 0, sizeof a)
typedef long long ll;
int n, m;
int A[MAXN];

struct line {
int k;
ll b;
line(int a = 0, ll b = 0) : k(a), b(b) {}
bool operator<(line x) { return k == x.k ? b < x.b : k < x.k; }
line operator+(line x) { return line(k + x.k, b + x.b); }
ll gval(ll x) { return k * 1ll * x + b; }
};
line bs[6000006], *cur;
int tot = 0;
struct MLE {
line* st;
int size;
void ini() { st = cur, size = 0; }
void fx() { cur = st + size; }
line& operator[](int a) { return *(st + a); }
void pop_back() { --size; }
void push_back(line r) {
*(st + size) = r;
++size;
}
} pmx[MAXN << 2], smx[MAXN << 2], mx[MAXN << 2];
ll S[MAXN << 2];

inline double cp(line a, line b) {
if (a.k == b.k)
return -1e18;
return (b.b - a.b * 1.) / (a.k - b.k);
}

inline void ins(MLE& s, line t) {
while (s.size > 1 && cp(s[s.size - 1], s[s.size - 2]) > cp(s[s.size - 1], t)) s.pop_back();
if (s.size == 1 && s[0].k == t.k)
s.pop_back();
s.pb(t);
}

MLE add(MLE& A, MLE& B) {
if (!A.size)
return B;
if (!B.size)
return A;
int p = 0, q = 0;
MLE re;
re.ini();
while (p + 1 < A.size || q + 1 < B.size) {
if (p + 1 == A.size) {
ins(re, A[p] + B[q]), ++q;
continue;
}
if (q + 1 == B.size) {
ins(re, A[p] + B[q]), ++p;
continue;
}
ins(re, A[p] + B[q]);
if (cp(A[p], A[p + 1]) < cp(B[q], B[q + 1]))
++p;
else
++q;
}
ins(re, A[p] + B[q]);
re.fx();
return re;
}

void build(int rt, int l, int r) {
if (l == r) {
mx[rt].ini(), mx[rt].pb(line(1, A[l])), mx[rt].fx();
smx[rt].ini(), smx[rt].pb(line(1, A[l])), smx[rt].fx();
pmx[rt].ini(), pmx[rt].pb(line(1, A[l])), pmx[rt].fx();
S[rt] = A[l];
return;
}
int m = l + r >> 1;
build(rt << 1, l, m), build(rt << 1 | 1, m + 1, r);
int j = 0;
MLE f;
f.ini();
rep(i, 0, mx[rt << 1].size - 1) {
while (j < mx[rt << 1 | 1].size && mx[rt << 1 | 1][j] < mx[rt << 1][i]) {
ins(f, mx[rt << 1 | 1][j]);
++j;
}
ins(f, mx[rt << 1][i]);
}
while (j < mx[rt << 1 | 1].size) ins(f, mx[rt << 1 | 1][j]), ++j;
f.fx();
MLE con = add(smx[rt << 1], pmx[rt << 1 | 1]);
j = 0;
mx[rt].ini();
rep(i, 0, f.size - 1) {
while (j < con.size && con[j] < f[i]) {
ins(mx[rt], con[j]), ++j;
}
ins(mx[rt], f[i]);
}
while (j < con.size) ins(mx[rt], con[j]), ++j;
mx[rt].fx();
pmx[rt].ini();
ll s = 0;
rep(i, l, r) s += A[i], ins(pmx[rt], line(i - l + 1, s));
pmx[rt].fx();
s = 0;
smx[rt].ini();
per(i, r, l) s += A[i], ins(smx[rt], line(r - i + 1, s));
smx[rt].fx();
S[rt] = S[rt << 1] + S[rt << 1 | 1];
}

struct que {
ll x;
int l, r, idx;
} Q[600006];

vector<ll> sl, sr, su;
ll sm;
ll px;

void doit(MLE& s) {
while (s.size > 1 && px > cp(s[0], s[1])) ++s.st, --s.size;
}

void gt(int rt, int len) {
if (len == 1) {
ll v = mx[rt][0].gval(px);
sm = max(sm, v);
sl.pb(v), sr.pb(v), su.pb(v);
return;
}
doit(mx[rt]), sm = max(sm, mx[rt][0].gval(px));
doit(smx[rt]), sl.pb(smx[rt][0].gval(px));
doit(pmx[rt]), sr.pb(pmx[rt][0].gval(px));
su.pb(S[rt] + len * 1ll * px);
}

void fuck(int rt, int l, int r, int L, int R) {
if (L <= l && R >= r) {
gt(rt, r - l + 1);
return;
}
int m = l + r >> 1;
if (L <= m)
fuck(rt << 1, l, m, L, R);
if (R > m)
fuck(rt << 1 | 1, m + 1, r, L, R);
}

ll as[600006];

void solve() {
// cout << sizeof( bs ) << ' ' << sizeof( line* ) << endl;
// cout << sizeof( line ) << endl;
cur = bs;
cin >> n >> m;
rep(i, 1, n) scanf("%d", A + i);
build(1, 1, n);
ll cx = 0;
int cn = 0;
rep(i, 1, m) {
int op, x, y;
scanf("%d", &op);
if (op == 1)
scanf("%d", &x), cx += x;
else
scanf("%d%d", &x, &y), ++cn, Q[cn] = (que){ cx, x, y, cn };
}
sort(Q + 1, Q + 1 + cn, [&](que a, que b) { return a.x < b.x; });
rep(i, 1, cn) {
ll tx = Q[i].x;
int l = Q[i].l, r = Q[i].r;
sm = 0;
px = tx;
su.clear(), sl.clear(), sr.clear();
fuck(1, 1, n, l, r);
int sz = su.size() - 1;
rep(j, 1, sz) su[j] += su[j - 1];
ll tmx = -1e18;
rep(j, 0, sz) {
if (j)
sm = max(sm, sr[j] + su[j - 1] + tmx);
tmx = max(tmx, sl[j] - su[j]);
}
as[Q[i].idx] = sm;
}
rep(i, 1, cn) printf("%lld\n", as[i]);
// cerr << cur - bs << endl;
}

signed main() {
// freopen("y0.in","r",stdin);
// freopen("out","w",stdout);
// int T;cin >> T;while( T-- ) solve();
solve();
}
文章作者: yijan
文章链接: https://yijan.co/2021/06/05/531-xun-lian-a-shi-shang-zui-xing-fu-de-nu-hai/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog