不算很难的题，但是调起来比较恶心。
下文默认下标从 \(1\) 开始。
设第 \(i\) 列长堤的高度为 \(h_i\)。考虑观察一些性质。
Observation 1：若 \(h_{i - 1} < h_i > h_{i + 1}\)，那么 \(h_i = n\) 一定不劣。
若 \(h_i < n\)，\([h_i + 1, n]\) 的鱼是抓不到的，并且增大 \(h_i\) 还有机会让旁边两列抓到更多的鱼，所以还不如 \(h_i = n\)。
Observation 2：若 \(h_{i - 1} > h_i < h_{i + 1}\)，那么 \(h_i = 0\) 一定不劣。
若 \(h_i > 0\)，\([1, h_i]\) 的鱼是抓不到的，让 \(h_i = 0\) 就能抓到 \([1, h_i]\) 的鱼。
Observation 3：对于一组连续的长堤，其一定是单峰的，并且其中 \(\max h_i = n, \min h_i = 0\)。
由上面两个观察易得。
Observation 4：\((i, h_i + 1)\) 一定有鱼。
如果 \((i, h_i + 1)\) 没有鱼，那我们能够增大 \(h_i\) 直到 \((i, h_i + 1)\) 有鱼，这样不会使第 \(i\) 列抓到更少的鱼，而且还有机会使旁边两列抓到更多的鱼。
然后我们就可以开始设计 dp 了。设 \(f_{i, j, 0/1}\) 为 \(h_i = j\)，\(h_i\) 处在上升还是下降阶段，能抓到的鱼的价值最大和。这里我们强制规定 \(h_i = n\) 时 \(h_i\) 处于下降阶段，\(h_i = 0\) 时 \(h_i\) 处于上升阶段。
转移大概就是，\(f_{i, j, 0}\) 从 \(\forall k \in [0, j], f_{i - 1, k, 0}\) 转移过来，差分一下加上第 \(i - 1\) 列中行坐标 \(\in [k + 1, j]\) 的鱼的价值和；\(f_{i, j, 1}\) 从 \(\forall k \in [j, n], f_{i - 1, k, 1}\) 转移过来，仍然差分一下加上第 \(i\) 列中行坐标 \(\in [j + 1, k]\) 的鱼的价值和。特别地，\(f_{i, 0, 0}\) 可以从任意 \(f_{i - 1, j, 1}\) 转移过来，\(f_{i, n, 1}\) 可以从任意 \(f_{i - 1, j, 0}\) 转移过来，加上第 \(i - 1\) 列行坐标 \(\in [j + 1, n]\) 的鱼的价值和。
对于价值和的计算，为了方便，我们强制规定，当 \(h_i\) 处于上升阶段时，\(f_i\) 计算 \([1, i - 1]\) 的价值和；\(h_i\) 处于下降阶段时，\(f_i\) 计算 \([1, i]\) 的价值和。但是这样有个问题，就是如果 \(h_{i - 1} > h_i = 0 < h_{i + 1}\) 且 \(h_{i - 1} > h_{i + 1}\)，我们的规定会导致第 \(i\) 列行坐标 \(\in [h_{i + 1} + 1, h_{i - 1}]\) 的鱼漏算进答案里面。这种情况我们直接从 \(f_{i - 2}\) 转移过来即可。
本质不同状态数只有 \(O(n + m)\) 种，因此使用 unordered_map 存储状态即可。
使用树状数组分别计算后缀和、前缀 \(\max\)、后缀 \(\max\)（记得每次转移完要清空），时间复杂度 \(O((n + m) \log n)\)。
code
// Problem: P8490 [IOI2022] 鲶鱼塘
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P8490
// Memory Limit: 2 MB
// Time Limit: 500000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 300100;
const ll inf = 0x3f3f3f3f3f3f3f3fLL;
ll n, m;
unordered_map<ll, ll> f[maxn][2];
vector<pii> vc[maxn];
struct BIT {
ll c[maxn];
inline void update(ll x, ll d) {
for (int i = x; i; i -= (i & (-i))) {
c[i] += d;
}
}
inline ll query(int x) {
ll res = 0;
for (int i = x; i <= n; i += (i & (-i))) {
res += c[i];
}
return res;
}
inline void clear(int x) {
for (int i = x; i; i -= (i & (-i))) {
c[i] = 0;
}
}
} t1;
struct mxBIT {
ll c[maxn], d[maxn];
inline void init() {
for (int i = 0; i < maxn; ++i) {
c[i] = d[i] = -inf;
}
}
inline void clear(int x) {
for (int i = (++x); i <= n + 1; i += (i & (-i))) {
c[i] = -inf;
}
for (int i = x; i; i -= (i & (-i))) {
d[i] = -inf;
}
}
inline void update(int x, ll y) {
for (int i = (++x); i <= n + 1; i += (i & (-i))) {
c[i] = max(c[i], y);
}
for (int i = x; i; i -= (i & (-i))) {
d[i] = max(d[i], y);
}
}
inline ll query1(int x) {
ll res = -inf;
for (int i = (++x); i; i -= (i & (-i))) {
res = max(res, c[i]);
}
return res;
}
inline ll query2(int x) {
ll res = -inf;
for (int i = (++x); i <= n + 1; i += (i & (-i))) {
res = max(res, d[i]);
}
return res;
}
} t2;
ll max_weights(int _n, int _m, vector<int> _x, vector<int> _y, vector<int> _w) {
n = _n;
m = _m;
for (int i = 0; i < m; ++i) {
int x = _x[i] + 1, y = _y[i] + 1, w = _w[i];
vc[x].pb(y, w);
}
f[0][0][0] = 0;
t2.init();
ll ans = 0;
for (int i = 1; i <= n; ++i) {
for (pii p : vc[i - 1]) {
t1.update(p.fst, p.scd);
}
vector<int> S;
for (pii p : f[i - 1][0]) {
if (p.scd < 0) {
continue;
}
S.pb(p.fst);
t2.update(p.fst, p.scd + t1.query(p.fst + 1));
}
for (pii p : vc[i]) {
if (p.fst == 1) {
continue;
}
int x = p.fst - 1;
f[i][0][x] = t2.query1(x) - t1.query(x + 1);
}
f[i][0][0] = t2.query1(0) - t1.query(1);
f[i][1][n] = t2.query1(n);
for (pii p : vc[i - 1]) {
t1.clear(p.fst);
}
for (int x : S) {
t2.clear(x);
}
vector<int>().swap(S);
if (i > 2) {
for (pii p : vc[i - 1]) {
t1.update(p.fst, p.scd);
}
for (pii p : f[i - 2][1]) {
if (p.scd < 0) {
continue;
}
S.pb(p.fst);
t2.update(p.fst, p.scd + t1.query(1) - t1.query(p.fst + 1));
}
for (pii p : vc[i]) {
if (p.fst == 1) {
continue;
}
int x = p.fst - 1;
f[i][0][x] = max(f[i][0][x], t2.query2(x));
}
f[i][0][0] = max(f[i][0][0], t2.query1(n));
for (pii p : vc[i - 1]) {
t1.clear(p.fst);
}
for (int x : S) {
t2.clear(x);
}
vector<int>().swap(S);
}
for (pii p : vc[i]) {
t1.update(p.fst, p.scd);
}
ll mx = 0;
for (pii p : f[i - 1][1]) {
if (p.scd < 0) {
continue;
}
mx = max(mx, p.scd);
t2.update(p.fst, p.scd - t1.query(p.fst + 1));
S.pb(p.fst);
}
for (pii p : vc[i]) {
if (p.fst == 1) {
continue;
}
int x = p.fst - 1;
f[i][1][x] = t2.query2(x) + t1.query(x + 1);
}
if (i == n) {
ans = max(ans, t2.query1(n) + t1.query(1));
}
f[i][0][0] = max(f[i][0][0], mx);
f[i][1][n] = max(f[i][1][n], t2.query2(n));
for (pii p : vc[i]) {
t1.clear(p.fst);
}
for (int x : S) {
t2.clear(x);
}
}
for (int i = 0; i <= 1; ++i) {
for (pii p : f[n][i]) {
ans = max(ans, p.scd);
}
}
return ans;
}
// int main() {
// int n, m;
// vector<int> a, b, c;
// scanf("%d%d", &n, &m);
// for (int i = 0, x, y, z; i < m; ++i) {
// scanf("%d%d%d", &x, &y, &z);
// a.pb(x);
// b.pb(y);
// c.pb(z);
// }
// printf("%lld\n", max_weights(n, m, a, b, c));
// return 0;
// }