[NOIP2023] 天天爱打卡 题解
Phartial
·
·
题解
设 l_i=x_i-y_i+1,r_i=x_i。
设 f_{i,0/1} 表示前 i 天中第 i 天不跑/跑时的最大收益。有转移方程：
对于 $f_{i,1}$ 的转移，为方便，我们可以将在转移 $f_{j,0}$ 的时候就将 $dj$ 加入其中，而对于 $\sum\limits_{j<l_u\le r_u\le i}v_u$，我们可以在转移前将所有满足 $r_u=i$ 的 $(l_u,r_u,v_u)$ 的贡献加入 $f_{j,0}$（即对所有 $j<l_u$ 的 $f_{j,0}$ 加上 $v_u$）。于是 $f_{i,1}$ 的转移就变成了简单的区间 $\max$，使用线段树维护 $f_{j,0}$ 即可，时间复杂度 $\mathcal{O}(n\log n)$，考虑优化。
注意到最终答案中我们必然只在形如 $[r_i+1,l_j-1]$ 的区间中不跑，且只在形如 $[l_i,r_j]$ 的区间中跑，因此决策点只可能是所有 $l_j-1$ 和 $r_j$，对所有 $l_i-1$ 和 $r_i$ 离散化，并只考虑这 $\mathcal{O}(m)$ 个位置即可。时间复杂度 $\mathcal{O}(m\log m)$。
```cpp
#include <algorithm>
#include <iostream>
using namespace std;
using LL = long long;
const int kM = 1e5 + 1, kN = kM * 2;
struct C {
int l, r, v;
bool operator<(const C &o) const { return r < o.r; }
} a[kM];
struct E {
LL mx, ta;
} e[kN << 2];
int cid, tt;
int n, m, k, v, b[kN];
LL d, f[kN];
void Pu(int x) { e[x].mx = max(e[x * 2].mx, e[x * 2 + 1].mx); }
void Pa(int x, LL v) { e[x].mx += v, e[x].ta += v; }
void Pd(int x) { Pa(x * 2, e[x].ta), Pa(x * 2 + 1, e[x].ta), e[x].ta = 0; }
void B(int x, int l, int r) {
e[x].ta = 0;
if (l == r) {
e[x].mx = (l ? -1e18 : 0);
return;
}
int m = l + r >> 1;
B(x * 2, l, m), B(x * 2 + 1, m + 1, r);
Pu(x);
}
void U(int x, int l, int r, int t, LL v) {
if (l == r) {
e[x].mx = v;
return;
}
Pd(x);
int m = l + r >> 1;
if (t <= m) {
U(x * 2, l, m, t, v);
} else {
U(x * 2 + 1, m + 1, r, t, v);
}
Pu(x);
}
void A(int x, int l, int r, int tl, int tr, LL v) {
if (l == tl && r == tr) {
Pa(x, v);
return;
}
Pd(x);
int m = l + r >> 1;
if (tl <= m) {
A(x * 2, l, m, tl, min(m, tr), v);
}
if (m < tr) {
A(x * 2 + 1, m + 1, r, max(m + 1, tl), tr, v);
}
Pu(x);
}
LL Q(int x, int l, int r, int tl, int tr) {
if (l == tl && r == tr) {
return e[x].mx;
}
Pd(x);
int m = l + r >> 1;
LL s = -1e18;
if (tl <= m) {
s = max(s, Q(x * 2, l, m, tl, min(m, tr)));
}
if (m < tr) {
s = max(s, Q(x * 2 + 1, m + 1, r, max(m + 1, tl), tr));
}
return s;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
for (cin >> cid >> tt; tt--;) {
cin >> n >> m >> k >> d;
v = 0;
for (int i = 1; i <= m; ++i) {
cin >> a[i].r >> a[i].l >> a[i].v;
a[i].l = a[i].r - a[i].l;
b[++v] = a[i].l, b[++v] = a[i].r;
}
sort(b + 1, b + v + 1);
v = unique(b + 1, b + v + 1) - b - 1;
for (int i = 1; i <= m; ++i) {
a[i].l = lower_bound(b + 1, b + v + 1, a[i].l) - b;
a[i].r = lower_bound(b + 1, b + v + 1, a[i].r) - b;
}
sort(a + 1, a + m + 1);
B(1, 0, v);
LL pm = 0;
for (int i = 1, j = 1, u = 0; i <= v; ++i) {
U(1, 0, v, i, pm + d * b[i]);
for (; j <= m && a[j].r == i; ++j) {
A(1, 0, v, 0, a[j].l, a[j].v);
}
for (; u < i && b[u] < b[i] - k; ++u) {
}
if (u < i) {
f[i] = Q(1, 0, v, u, i - 1) - d * b[i];
} else {
f[i] = -1e18;
}
pm = max(pm, f[i]);
}
cout << pm << '\n';
}
return 0;
}
```